C / C++ Program for Largest Sum Contiguous Subarray
Write a C/C++ program for a given array arr[] of size N. The task is to find the sum of the contiguous subarray within a arr[] with the largest sum.
C / C++ Program for Largest Sum Contiguous Subarray using Kadane’s Algorithm:
The idea of Kadane’s algorithm is to maintain a variable max_ending_here that stores the maximum sum contiguous subarray ending at current index and a variable max_so_far stores the maximum sum of contiguous subarray found so far, Everytime there is a positive-sum value in max_ending_here compare it with max_so_far and update max_so_far if it is greater than max_so_far.
So the main Intuition behind Kadane’s algorithm is
- The subarray with negative sum is discarded (by assigning max_ending_here = 0 in code).
- we carry subarray till it gives positive sum.
Initialize:
max_so_far = INT_MIN
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
(c) if(max_ending_here < 0)
max_ending_here = 0
return max_so_far
Illustration:
Lets take the example:
{-2, -3, 4, -1, -2, 1, 5, -3}
max_so_far = max_ending_here = 0
for i=0, a[0] = -2
max_ending_here = max_ending_here + (-2)
Set max_ending_here = 0 because max_ending_here < 0
for i=1, a[1] = -3
max_ending_here = max_ending_here + (-3)
Set max_ending_here = 0 because max_ending_here < 0
for i=2, a[2] = 4
max_ending_here = max_ending_here + (4)
max_ending_here = 4
max_so_far is updated to 4 because max_ending_here greater
than max_so_far which was 0 till now
for i=3, a[3] = -1
max_ending_here = max_ending_here + (-1)
max_ending_here = 3
for i=4, a[4] = -2
max_ending_here = max_ending_here + (-2)
max_ending_here = 1
for i=5, a[5] = 1
max_ending_here = max_ending_here + (1)
max_ending_here = 2
for i=6, a[6] = 5
max_ending_here = max_ending_here + (5)
max_ending_here = 7
max_so_far is updated to 7 because max_ending_here is
greater than max_so_far
for i=7, a[7] = -3
max_ending_here = max_ending_here + (-3)
max_ending_here = 4
Follow the below steps to Implement the idea:
- Initialize the variables max_so_far = INT_MIN and max_ending_here = 0
- Run a for loop from 0 to N-1 and for each index i:
- Add the arr[i] to max_ending_here.
- If max_so_far is less than max_ending_here then update max_so_far to max_ending_here.
- If max_ending_here < 0 then update max_ending_here = 0
- Return max_so_far
Below is the Implementation of the above approach.
C++
// C++ program to print largest contiguous array sum #include <climits> #include <iostream> using namespace std; int maxSubArraySum( int a[], int size) { int max_so_far = INT_MIN, max_ending_here = 0; for ( int i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here) max_so_far = max_ending_here; if (max_ending_here < 0) max_ending_here = 0; } return max_so_far; } /*Driver program to test maxSubArraySum*/ int main() { int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = sizeof (a) / sizeof (a[0]); int max_sum = maxSubArraySum(a, n); cout << "Maximum contiguous sum is " << max_sum; return 0; } |
Maximum contiguous sum is 7
Output:
Maximum contiguous sum is 7
Time Complexity: O(n)
Auxiliary Space: O(1)
Print the Largest Sum Contiguous Subarray:
To print the subarray with the maximum sum the idea is to maintain start index of maximum_sum_ending_here at current index so that whenever maximum_sum_so_far is updated with maximum_sum_ending_here then start index and end index of subarray can be updated with start and current index.
Follow the below steps to implement the idea:
- Initialize the variables s, start, and end with 0 and max_so_far = INT_MIN and max_ending_here = 0
- Run a for loop from 0 to N-1 and for each index i:
- Add the arr[i] to max_ending_here.
- If max_so_far is less than max_ending_here then update max_so_far to max_ending_here and update start to s and end to i .
- If max_ending_here < 0 then update max_ending_here = 0 and s with i+1.
- Print values from index start to end.
Below is the Implementation of above approach:
C++
// C++ program to print largest contiguous array sum #include <climits> #include <iostream> using namespace std; void maxSubArraySum( int a[], int size) { int max_so_far = INT_MIN, max_ending_here = 0, start = 0, end = 0, s = 0; for ( int i = 0; i < size; i++) { max_ending_here += a[i]; if (max_so_far < max_ending_here) { max_so_far = max_ending_here; start = s; end = i; } if (max_ending_here < 0) { max_ending_here = 0; s = i + 1; } } cout << "Maximum contiguous sum is " << max_so_far << endl; cout << "Starting index " << start << endl << "Ending index " << end << endl; } /*Driver program to test maxSubArraySum*/ int main() { int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = sizeof (a) / sizeof (a[0]); maxSubArraySum(a, n); return 0; } |
Maximum contiguous sum is 7 Starting index 2 Ending index 6
C / C++ Program for Largest Sum Contiguous Subarray using Dynamic Programming:
C++
// C++ program to print largest contiguous array sum #include <bits/stdc++.h> using namespace std; void maxSubArraySum( int a[], int size) { vector< int > dp(size, 0); dp[0] = a[0]; int ans = dp[0]; for ( int i = 1; i < size; i++) { dp[i] = max(a[i], a[i] + dp[i - 1]); ans = max(ans, dp[i]); } cout << ans; } /*Driver program to test maxSubArraySum*/ int main() { int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = sizeof (a) / sizeof (a[0]); maxSubArraySum(a, n); return 0; } |
7
Output:
Maximum contiguous sum is 7
Time Complexity: O(n)
Auxiliary Space: O(1)
Practice Problem:
Given an array of integers (possibly some elements negative), write a C program to find out the *maximum product* possible by multiplying ‘n’ consecutive integers in the array where n ? ARRAY_SIZE. Also, print the starting point of the maximum product subarray.
Please refer complete article on Program for Largest Sum Contiguous Subarray for more details!