Friday, September 12, 2014

Maximum subsequence sum


import java.util.ArrayList;

/**
 * Created by Arun on 9/11/14.
 */
public class SequenceResult
{
    public static void maximumContSubSeq(int[] a) {
        int sum[] = new int[a.length]; // Sum at every element
        sum[0] = a[0];
        int max = 0;
        for (int i = 1; i < a.length; i++) {
            sum[i] = Math.max(sum[i - 1] + a[i], a[i]);
            if(sum[i-1]+a[i]>a[i]){
                sum[i] = sum[i - 1] + a[i];
            }
            if (max < sum[i]) {
                max = sum[i];
            }
        }
        System.out.println(max);
    }


    public static void main(String args[]){
        int x[] = {-2, 3, -16, 100, -4, 5, 21 };
        maximumContSubSeq(x);
    }

}

No comments:

Post a Comment