C++ Program to Find the maximum subarray sum O(n^2) time(naive method)

«
»

C++ Program to find the maximum sub-array sum O(n^2) time(naive method).

Problem Description

1. Implement the naive method to find the sub-array having a maximum sum.
2. The worst case time complexity of the algorithm is O(n*n).

Problem Solution

1. Take the input of the integer array.
2. Compare the sum of elements of every sub-array of length 1 to n.
3. Print the sub-array with maximum sum.
4. Exit.

advertisement
Program/Source Code

C++ program to find the maximum sub-array sum O(n^2) time(naive method).
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#include<iostream>
 
using namespace std;
 
int main()
{
	int n, i, j, max=-1, sum, imax, fmax;
	cout<<"\nEnter the number of data element in the array: ";
	cin>>n;
 
    int a[n];
	for(i = 0; i < n; i++)
	{
		cout<<"Enter element "<<i+1<<": ";
		cin>>a[i];
	}
 
	// Loop for the length of the sub-array.
	for(i = 1; i < n+1; i++)
	{
		sum = 0;
		// Loop for the maximizing the sum of the element of the sub array of length 'i'.
		for(j = 0; j < n; j++)
		{
			// First pick the first sub array of 'i' length.
			if(j < i)
				sum += a[j];
			// Add the next element and subtract the first element from the sub-array.
			else
				sum = sum+a[j]-a[j-i];
 
			// Compare the sum with the global maximum of each length.
			if(max < sum )
			{
				// Assign the initial and the final indexes to the imax and the fmax variables and update the max, if condition satisfies.
				imax = j-i+1;
				fmax = j;
				max = sum;
			}
		}
	}
 
	// Print the maximum sum sub-array and their sum.
	cout<<"\nThe maximum sub array is: ";
	for(i = imax; i <= fmax; i++)
		cout<<a[i]<<" ";
	cout<<"\nThe maximum sub-array sum is: "<<max;
}
Program Explanation

1. Take the input of the array of ‘n’ data element.
2. A loop for the length of the sub-array from 1 to n.
3. In another loop nested with the previous one, calculate the sum of first sub-array of that length.
4. For remaining sub-array sum, add the next element to the sum and subtract the first element of that sub-array.
5. Now compare it with the global max and update if found out to be more.
6. Print the max sub-array and their sum as a result.
7. Exit.

advertisement
Runtime Test Cases
Case 1:
Enter the number of data element in the array: 10
Enter element 1: 2
Enter element 2: 2
Enter element 3: -5
Enter element 4: 4
Enter element 5: -5
Enter element 6: -6
Enter element 7: -7
Enter element 8: 8
Enter element 9: 8
Enter element 10: -16
 
The maximum sub-array is: 8 8
The maximum sub-array sum is: 16

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn