MAXSUM problem

Q.:- find the contiguous sub array within an array which has the largest sum.

for example :- [−2,1,−3,4,−1,2,1,−5,4]
sub array which has the largest sum (6) = [4, -1 ,2 ,1 ]

Solution:- Code snippet :=
IN C lang –

</strong>int max(int x, int y)
{ return (y > x)? y : x; }

int maxSubArray(const int* A, int n1) {
int maxc = A[0], i;
int curr_max = A[0];

for (i = 1; i < n1; i++)
{
curr_max = max(A[i], curr_max+A[i]);
maxc = max(maxc, curr_max);
}
return maxc;

}

IN JAVA :=

<br />class MaxsumSolution {
public:
int maxSubarrat(const vector<int> &A) {
int n=A.size();
int cursum=0, maxSum=-1000000000;

for(int i =0; i<n ;i++) {
curSum = curSum + A[i];
maxSum = max(maxSum, curSum);
if(curSum<0)
curSum = 0;
}
return maxSum;
}
};

Asked in :- Facebook, Paypal, Yahoo, Microsoft, LinkedIn .