CareerCup

We can solve this problem using Kandane's algorithm

max_subarray(A){
    max_so_far = max_ending_here = 0
    for x in A:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Its simple. Find the sum until the sum gets negative. When the sum gets negative start from zero.

Eg: 2,3 , -2 , 4 , -8 , 8, 9, -2, 10

1: Initially the sum is 2 (first no.). Start from second if first no. is zero and so on.
2: Keep adding the number until the sum is negative. (2+3-2 + 4) =7 but adding -8 gives sum = -1 so start from zero.
3: Repeat step 2 again. Now the sum is 8 + 9 -2 + 10 =25. This is max contiguous sum.

Note: do not include the last no. in sum if it is negative.

Complexity: O(n)

package programs;
import java.util.Scanner;

public class dynamicprogram2 {
static int[] sequence;
static int[] memory;
public static int MaxSum(int[] x)
{
int len = x.length;
int max=0;
int status = 0;
int temp;
memory[0]=sequence[0];
//int temp;
for (int i=0;i<len;i++)
{
if(sequence[i]>0)
{
status =1;
break;
}
}
if(status == 1)
{
for (int i=1;i<len;i++)
{
temp=memory[i-1]+sequence[i];
if(temp>0)
{
memory[i] = temp;
if(max<memory[i])
max = memory[i];

}
else
memory[i]=0;
}

}
else
{
max = sequence[0];
for (int i=1;i<len;i++)
{
if(sequence[i]>max)
max = sequence[i];
}

}
return max;
}
public static void main(String[] args)
{
int length = 0;
Scanner a = new Scanner(System.in);
System.out.println("Enter the length of your sequence: ");
length = a.nextInt();
sequence = new int[length];
memory = new int[length];
for(int i=0;i<sequence.length;i++)
{
memory[i] = 0;
}
System.out.println("Enter the element of your sequence one by one: ");
for(int i=0;i<sequence.length;i++)
{
sequence[i] = a.nextInt();
}
System.out.println("Maximum contiguous sub-sequence sum of the given sequence is : "+ MaxSum(sequence));
}

}

#include <iostream>
using namespace std;

int max(int a,int b)
{
	return (a>b)?a:b;
}

int contg_sum(int *arr,int length)
{
	if(length<0){cout<<"ERROR, Length of array cannot be negative";return -1;}
	if(length==0){return 0;}
	int sum_so_far=arr[0];
	int max_so_far=arr[0];
	for (int i=1;i<length;i++)
	{
		sum_so_far=max(sum_so_far+arr[i],arr[i]);
		max_so_far=max(max_so_far,sum_so_far);
	}
	return max_so_far;
}

int main()
{
	int array[]={2,3,4,2,-11,4,6};
	int t=contg_sum(array,7);
	cout<<t;
}

An implementation based on what user "androidify" stated above.

Below code works for all cases.

#define ERROR -1
int maxSum_subArray(const int * arr, const int arrSize) {
    int i;
    int currentMax;
    int maxsoFar;

    if((NULL == arr) || (arrSize <= 0)) {
        printf("\n\n"); printf(" ERROR! "); printf("\n\n");
        return ERROR;
    }

    currentMax=0;
    maxsoFar=INT_MIN;
    for(i=0; i<arrSize; ++i) {

        currentMax += arr[i];

        if(currentMax > maxsoFar) {
            //printf("\n\n"); printf(" maxsoFar at i = %d, currentMax = %d", i, currentMax); printf("\n\n");
            maxsoFar = currentMax;
        }

        if(currentMax < 0) {
            //printf("\n\n"); printf(" -ve currentMax at i = %d", i); printf("\n\n");
            currentMax=0;
        }
    }

    return maxsoFar;
}

meet this problem in my online test for summer intern

Python working code, using max()

"""
1:45

Written round question for Epic systems. They asked two dynamic programming problems. 
Write a dynamic programming solution for finding maximum contiguous sub-sequence sum.
"""
class MaxSub(object):
  def __init__(self, listNum):
    if listNum is None:
      print 'Invalid!'
      raise SystemExit
      
    self._listNum = listNum
    
  def getMaxSum(self):
    curMax = 0
    maxMax = 0
    for num in self._listNum:
      curMax = max(num, curMax + num)
      maxMax = max(maxMax, curMax)
      
    return maxMax
    
m = MaxSub([2, 3 , -2 , 4 , -8 , 8, 9, -2, 10])
print m.getMaxSum()

public class MaxContSum {

    public static void main(String[] args) {
        int[] array = new int[]{2, 3, -2, 4, -8, 8, 9, -2, 10};
        int[] sum = new int[array.length];
        int max = array[0];
        sum[0] = array[0];
        int start=0,end=0;
        for (int i = 1; i < array.length; i++) {


            if (array[i] < sum[i - 1] + array[i]) {
                sum[i] = sum[i - 1] + array[i];
            } else {
                 sum[i] = array[i];
                start=i;
            }

            if (max < sum[i ])
            {
                max = sum[i ];
                end=i;
            }


        }

        System.out.println(max+" starts at "+start+" ends at "+end);
    }

}

onestopinterviewprep.blogspot.com/2014/03/namespace-arrayproblem-write-function.html

You can understand the solution to this problem by watching this wonderful video tutorial on maximum sub sequence problem
youtube.com/watch?v=hXlv88ddcgw

Using Dynamic Algorithm ,
sum[i] for each element i = sum(all elements till o to i)
maxStartIndexArray[i] = index of start of the subarray.

int inputLength = this.input.length;
	
int[] sum = new int[inputLength];
int[] maxStartIndexArray = new int[inputLength];

//S[i+1] = max(S[i] + A[i+1], A[i+1]) 
//S[0]   = A[0]

sum[0] = input[0];
int maxSum = sum[0];
int maxStartIndex = 0;
int maxEndIndex = 0;
int current;
for(int index = 1 ; index < inputLength - 1 ; index++){
	if(sum[index - 1] > 0)
	{
//S[1] = S[0] + INPUT[1]
sum[index] = sum[index -1] + input[index];
maxStartIndexArray[index] = maxStartIndexArray[index -1];
	}else{
     //since current value is negative we end the max-substring.
     //new max substring beings at the current index
      sum[index] = input[index];
       maxStartIndexArray[index] = index;
	}
if(sum[index] > maxSum){
         maxSum = sum[index];
         maxStartIndex = maxStartIndexArray[index];
         maxEndIndex = index;
	}
}
System.out.println("MaxSum :" + maxSum);
System.out.println("Start Index :" + maxStartIndex);
System.out.println("End Index :" + maxEndIndex);