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;} |
Output
Maximum contiguous sum is 7 Starting index 2 Ending index 6
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.