/** Author : Siddhant Swarup Mallick
 * Github : https://github.com/siddhant2002
 */

/** Program description - To find the maximum subarray sum */
 package com.thealgorithms.dynamicprogramming;

public class KadaneAlgorithm {
    public static boolean max_Sum(int a[] , int predicted_answer)
    {
        int sum=a[0],running_sum=0;
        for(int k:a)
        {
            running_sum=running_sum+k;
            // running sum of all the indexs are stored
            sum=Math.max(sum,running_sum);
            // the max is stored inorder to the get the maximum sum
            if(running_sum<0)
            running_sum=0;
            // if running sum is negative then it is initialized to zero
        }
        // for-each loop is used to iterate over the array and find the maximum subarray sum
        return sum==predicted_answer;
        // It returns true if sum and predicted answer matches
        // The predicted answer is the answer itself. So it always return true
    }
    /**
     * OUTPUT :
     * Input - {89,56,98,123,26,75,12,40,39,68,91}
     * Output: it returns either true or false
     * 1st approach Time Complexity : O(n)
     * Auxiliary Space Complexity : O(1)
     */
}