All Courses
AI Career Planner
1:1 Coaching/Mentoring
Job Board
SQL
HTML/CSS/JS
Coding
Settings
LogoutHello Everyone,
Write an efficient program to find the sum of contiguous subarray within a one-dimensional array of numbers that has the largest sum.
Another approach:
int maxSubarraySum( int arr[], int size)
{
int max_ending_here = 0, max_so_far = INT_MIN;
for ( int i = 0; i < size; i++) {
// include current element to previous subarray only
// when it can add to a bigger number than itself.
if (arr[i] <= max_ending_here + arr[i]) {
max_ending_here += arr[i];
}
// Else start the max subarry from current element
else {
max_ending_here = arr[i];
}
if (max_ending_here > max_so_far)
max_so_far = max_ending_here;
}
return max_so_far;
} // contributed by Vipul Raj
Time Complexity: O(n)
Algorithmic Paradigm: Dynamic Programming
Following is another simple implementation suggested by Mohit Kumar. The implementation handles the case when all numbers in the array are negative.
#include<iostream>
using namespace std;
int maxSubArraySum( int a[], int size)
{
int max_so_far = a[0];
int curr_max = a[0];
for ( int i = 1; i < size; i++)
{
curr_max = max(a[i], curr_max+a[i]);
max_so_far = max(max_so_far, curr_max);
}
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;
}
Output:
Maximum contiguous sum is 7
To print the subarray with the maximum sum, we maintain indices whenever we get the maximum sum.
// C++ program to print largest contiguous array sum
#include<iostream>
#include<climits>
using namespace std;
int 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]);
int max_sum = maxSubArraySum(a, n);
return 0;
}
Output:
Maximum contiguous sum is 7 Starting index 2 Ending index 6
Time Complexity: O(n)
Auxiliary Space: O(1)