package dynamicprogramming;


public class LargestSumSubarray {

    /*
     * Given an array, find the contiguous subarray with the largest sum.
     * Input: -4, 2,-5,1,2,3,6,-5,1
     * Output: the largest sum subarray starts at index 3 and ends at 6 and the largest sum is 12
     *
     *
     * Below solution has:
     * Runtime Complexity - Linear, O(n).
     * Memory Complexity - Constant, O(1).
     *
     * This can be solved by Kadane's algorithm:
     * Basic idea of Kadane's algorithm is scanning the entire array and at each position finding the maximum sum of
     * subarray ending there.
     * This is achieved by keeping a current maximum for the current array index and a global maximum.
     * */
    public static int getLargestSumFromArray(int[] arr) {
        int maxSoFar = 0;
        int maxAtEnd = 0;

        for(int i=0; i<arr.length; i++) {
            maxSoFar = Math.max(0, arr[i] + maxSoFar);
            maxAtEnd = Math.max(maxAtEnd, maxSoFar);
        }

        return maxAtEnd;
    }



    public static void main(String[] args) {
        int[] arr = {-4, 2, -5, 1, 2, 3, 6, -5, 1};
        System.out.println(getLargestSumFromArray(arr));
    }
}