Hello 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)