Alg.4 Kadane's Algorithm

From algoexpert.io

In this problem, we have to write a function to get a given array’s maximum sum of its subarray. So, in this case, Kadane’s Algorithm would be an efficient option for this one.

Assume we have an non-empty array, “array”, first, we need to iterate this array, use a variable “currentSum” to record the current maximum sum. Obviouly, the maximum sum would be either the current element array[i] or ans + array[i]. We almost finish this problrm here, the last thing we need to do is to find the biggest “currentSum” while we iterate this array.

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

Time complexity: O(n); Space complexity: O(1)

Donate