C++ Program to Find the Maximum Subarray Sum using 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.

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
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
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.