CareerCup

1. Just keep track of max_sum, max_start and max_end so far.
2. Keep storing new sum in temp_sum and new start in new_start new end will be "i".
3. If temp_sum is greater than max_sum update all max variables.

O(n) and done in place....
Here is an implementation in java...

docs.google.com/open?id=0Bw6L8Yy5eLJ3MUQxM3B2MVNEMkE

void MaxSubSeq(int array[],int length, int *start, int *end)

{
//    long long max_sum = -(~((long long)0));
    long long max_sum = -(((long long)1)<<(8*sizeof(int)));
    long long entire_sum=0;
    int break_point = -1,i=0;

    for(; i<length; i++)
    {
        entire_sum += array[i];
        printf("entire_sum = %lld\n",entire_sum);
        if(max_sum < entire_sum)
        {
            max_sum = entire_sum;
            printf("Max_Sum = %lld\n",max_sum);

            *start = break_point+1;
            *end = i;
        }
        if(entire_sum <= 0)
        {
            entire_sum = 0;
            break_point = i;
        }
    }
}

void maxSum(int a[], int n)
{
    int max=-9999, curr=0,start=0,end=0,currentstart=0;
    for(int i=0;i<n;i++)
    {
        curr+=a[i];
        if(curr>max)
        {
            max = curr;
            start=currentstart;
            end = i;
        }
        else if(curr<0)
        {
            currentstart=i+1;
            curr=0;
        }
    }
    cout<<max<<" "<<start<<" "<<end<<endl;
}

I think this does the trick in O(N).

public class GetMaxSubsequence2 {
	public static void main (String [] args)
	{
		int [] arr = {1, 3, 5, -2, 6, -2, -4, -8, 2, 3, -1, -1, 4, 5, 9};		
		getMaxSubSeq2(arr);
		
		int [] arr2 = {10, 10, 10, 10, 10, 10, 10, -71, 71};
		getMaxSubSeq2(arr2);
		
		int [] arr3 = {-5, 8, 9, -3, -6, 2, 4, -8, 1};
		getMaxSubSeq2(arr3);
	}
		
	public static int [] getMaxSubSeq2(int [] arr)
	{
		int maxSeqStart = 0;
		int maxSeqStop = 0;
		int maxSeqValue = 0;
		
		int curSeqStart = 0;
		int curSeqValue = 0;
		
		int at = 0;
		while(at < arr.length)
		{
			if(curSeqStart == -1)
			{
				curSeqStart = at;
				curSeqValue = 0;
			}
			curSeqValue += arr[at];
			if(curSeqValue >= maxSeqValue)
			{
				maxSeqStart = curSeqStart;
				maxSeqStop = at;
				maxSeqValue = curSeqValue;
			}
			if(curSeqValue < 0)
			{
				curSeqStart = -1;
				maxSeqValue = 0;
			}
			at++;
		}

		System.out.println("Max subsequence goes from " + maxSeqStart + " to " + maxSeqStop + " and has value " + maxSeqValue);
		for(int i = maxSeqStart; i <= maxSeqStop; i++)
		{
			System.out.print(arr[i] + ", ");
		}
		System.out.println();
		int lu[] = new int[2];
		lu[0] = maxSeqStart;
		lu[1] = maxSeqStop;
		return lu;
	}

}

qqq

Read up on Kandane's Algo

KADANE ALGORITHM