CareerCup

Its sinmple.
Start adding from first element till last element. After every addition check if sum is negative. If it is than make it zero (neglect all values b4). Also have a max variable which keeps track of the max sum till now.

max=sum=0;
for (i=0; i< arraySize; ++i)
{ sum+=arr[i];
if (sum < 0)
sum = 0;
if (sum > max)
max = sum;
}

This code works with O(Nsquare) time.
maxsum = 0;
sum = 0;
for(i=0;i<n;i++)
{
sum = 0;
for(j=i;j<n;j++)
{
sum = array[j] + sum;
maxsum = max(sum,maxsum);
}
}

Go buy the programming pearls book by Bentley. That has this and more interesting stuff.

Just keep summing until negative, keeping track of the max as you go. If you become negative, restart at 0.

what if array consists of all -ve numbers all of these sol break

This algorithm does not if all the given numbers are -ve. Eg: -1, -2, -3. The above algo says max sum is: 0. Please correct me if I am missing anything.

#include<stdio.h>
int maxsum(int *a,int n)
{
int max,sum,i=0;
max=sum=a[i];
for(i=1;i<n;i++)
{
sum=sum+a[i];
if(max<sum)
max=sum;
if(sum<0)
sum=0;
}
return max;
}
main()
{
int a[]={2,-3,4,-5,6,-3,8};
printf("sum = %d\n",maxsum(a,7));
return 0;
}

I believe its asked to return int array with continuous sequence of elements whose sum is max and not the sum of those elements. Here is what I came up with (did not implement case with all -ve numbers though). Complexity is O(n^2).

public static int[] FirstConsecutiveSequenceWithMaxSum(int[] inputArray)
        {
            //local variables
            int _startIndex=0, _endIndex=0;
            int _currentMax=0, _newLoopSum=0;
            int l = inputArray.Length; //input array size
            int[] _returnArray;
            //boundary case.
            if (l == 0)
            {
                //throw exception or 
                //return blank array 
                //as per user requirements
                //TODO 
            }
            if (l == 1)
            {
                return inputArray;
            }

            for (int i = 0; i < l; i++)
            {
                if (inputArray[i] > 0)
                {
                    for (int j = i; j < l; j++)
                    {
                        _newLoopSum += inputArray[j];

                        if (_newLoopSum > _currentMax)
                        {
                            _currentMax = _newLoopSum;
                            _startIndex = i;
                            _endIndex = j;
                        }
                    }
                    //reset current loop sum
                    _newLoopSum = 0;
                }
            }

            if ((_endIndex-_startIndex)==0)
            {
                //all are negative numbers.
                //TODO as per the requirements
            }

            int _returnArrayLength = _endIndex - _startIndex + 1;
            _returnArray = new int[_returnArrayLength];
            for (int i = 0; i < _returnArrayLength; i++)
            {
                _returnArray[i] = inputArray[_startIndex++];
            }

            return _returnArray;

}

I am not sure if you need this check
if (inputArray[i] > 0)
Consider this Array {3, -2, 10, -3} Here the answer is {3, -2, 10}.

int sub1[40]= { -2, -3, 5, 7, -1, 0, 17, -9,3, -29,
1, 0, -9, -41, 3, 7, 13, -9, 11, -6,
71,-3, -9, -8, 87, 9, 1, 7, -1, -3,
10, 9, 11, -9, -27, 1, 0, -39, 1, 14 };
// max sub = {71,-3, -9, -8, 87, 9, 1, 7, -1, -3,10, 9, 11}
// 20th to 32nd, sum = 144

void findSub(int a[40])
{
int i = 0;
int tempSum =0;
maxSub myMax;
myMax.start = 0;
myMax.end = 0;
myMax.max = a[0];
while (i<40)
{
i++;
if (myMax.max <= 0 )
{
if (a[i] >= myMax.max)
{
myMax.start = i;
myMax.end = i;
myMax.max = a[i];
cout << " start: " << myMax.start <<" end: " << myMax.end;
cout << " max = " << myMax.max <<endl;

}
}
else
{
if (a[i] > 0)
{
myMax.end = i;
myMax.max += a[i];
}
else
{
tempSum += a[i];
while (i<40)
{
i++;
if (a[i]<=0)
tempSum += a[i];
else
{
if (a[i]>= myMax.max)// reset
{
myMax.start = i;
myMax.end = i;
myMax.max += a[i];
cout << " start: " << myMax.start <<" end: " << myMax.end;
cout << " max = " << myMax.max <<endl;
}
else
{
tempSum += a[i];
if (tempSum >=0) // expand the sub_array
{
myMax.end = i;
myMax.max += tempSum;
tempSum = 0;
cout << " start: " << myMax.start <<" end: " << myMax.end;
cout << " max = " << myMax.max <<endl;
}
}
} // new positive number
} // search and expand
} // deal with negative
} // positive sum
}
}

http://www.cs.ucf.edu/~reinhard/classes/cop3503/lectures/AlgAnalysis04.pdf

int main()
{
int a[100],n,sum=0,max;
cout<<"Enter the no of elements\n";cin>>n;
for(int i=0;i<n;i++)cin>>a[i];max=a[0];
for(int j=0;j<n;j++)
{
sum+=a[j];
if(sum<0)sum=0;
if(a[j]>max)max=a[j];
if(sum>max && sum!=0)max=sum;
}
cout<<max<<"\n";
return 0;
}

The above code is short,simple and correct..

Its a DP problem,

let,
a[j]->given array
m[j]->max value array

m[j]=max(m[j],m[j-1]+a[j])-------> O(n)
call it recursively and scan m[] to get the maximum---------> O(n)

O(n) solution

public static int MCSS(int [] a) {
int max = 0, sum = 0, start = 0, end = 0, i=0;
// Cycle through all possible end indexes.
for (j = 0; j < a.length; j++) {
sum += a[j]; // No need to re-add all values.
if (sum > max) {
max = sum;
start = i; // Although method doesn't return these
end = j; // they can be computed.
}
else if (sum < 0) {
i = j+1; // Only possible MCSSs start with an index >j.
sum = 0; // Reset running sum.
}
}
return max;
}