Find the largest sum in an Array Problem

You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum.

EXAMPLE

input: {2, -8, 3, -2, 4, -10}
output: 5 [ eg, {3, -2, 4} ]

Answer  :


You might have identified that dynamic programming is appropriate for this problem. Let’s write down the recurrence:

sum(i,j) = max_k sum(i,k) + sum(k+1, j)

This will give an O(N^3) solution. A brute force summing of the sequences will give the same time.

A simple linear algorithm will work by keep track of the current subsequence sum. If that sum ever drops below zero, that subsequence will not contribute to the subsequent maximal subsequence since it would reduce it by adding the negative sum.

public class SumArr {

    public static void main(String[] args) {
        int a[] = {6,-8, 3, -2, 4};
        int maxsum = 0;
        int sum = 0;
        for (int i = 0; i < a.length; i++) {
        sum += a[i];
        if (maxsum < sum) {
        maxsum = sum;
        } else if (sum < 0) {
        sum = 0;
        }
        }
        System.out.println(maxsum);
    }
}

Click For Answer