Size of subarray with max sum code in C++.

Write a program to find the size of subarray with maximum sum in given array.

 

This program is variation of largest sum contigous sub-array.

Given an input array we have to find the size of subarray which has maximum sum.

Input Specifications is as follows:- First line of Input contains the size of array.
Second Line of Input contains n spaced Integers .

Output contains a single Integer k where k denotes the size of sub-array with maximum sum.

 

Solution

Readers are requested to try the code before viewing the solution . They  can submit their codes in comment section below.

Approach:

The best way to solve this puzzle is to use Kadane’s algorithm which runs in O(n) time. The idea is to keep scanning through the array and calculating the maximum sub-array that ends at every position. The sub-array will either contain a range of numbers if the array has intermixed positive and negative values, or it will contain the least negative value if the array has only negative values. we need to keep track of starting index as well as end index while applying kadane’s algorithm.

 

code:-

 

[code language=”cpp”]

#include <iostream>
using namespace std;

int main() {
// your code goes here
int i,n;
int start,end;
int s;
int max_ending_here=0;
int max_so_far=0;
cin>>n;int a[n];
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
{
max_ending_here+=a[i];
if(max_ending_here >max_so_far)
{
max_so_far=max_ending_here;
start=s;
end=i;

}
else if(max_ending_here<0)
{
max_ending_here=0;
s=i+1;
}

}

cout<<start-end+1<<endl;
return 0;
}

[/code]

The time complexity for this approach is O(n).

 

Please Login/Signup to comment