C++ Programming Code Examples

C++ > Sorting Searching Code Examples

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

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

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

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

#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;
}