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