package algoexpert.medium;

/*
PROBLEM:
Find max sum from an non-empty sub-array (only adjacent elements)  

EXAMPLE:
[3,5,-9,1,3,-2,3,4,7,2,-9,6,3,1,-5,4] -> 19 (1,3,-2,3,4,7,2,-9,6,3,1)

Solution:
1. time : O(n) | space : O(1)
find maxSum possible at each index (include or start new)

*/

public class Kadane
{
    public static void test()
    {
        System.out.println(kadanesAlgorithm(new int[] {3,5,-9,1,3,-2,3,4,7,2,-9,6,3,1,-5,4}));
    }

    public static int kadanesAlgorithm(int[] array)
    {
        int current = array[0];
        int maxSum = current;
        for (int i = 1; i < array.length; ++i)
        {
            current = Math.max(array[i], current + array[i]);
            if (current > maxSum) { maxSum = current; }
        }
        return maxSum;
    }
}