Kadane's Algorithm

Time: O(n)

Space: O(1)

Intuition

Maximum subarray sum. At each position, decide: extend the current subarray or start fresh. If the running sum becomes negative, starting fresh is always better. dp[i] = max(nums[i], dp[i-1]+nums[i]).

Algorithm

1maxSum = currentSum = arr[0].
2For i from 1 to nâˆ’1: currentSum = max(arr[i], currentSum+arr[i]).
3maxSum = max(maxSum, currentSum).
4Return maxSum.

Example Walkthrough

Input: arr = [-2,1,-3,4,-1,2,1,-5,4]

1.cur: -2â†’1â†’-2â†’4â†’3â†’5â†’6â†’1â†’5. maxSum=6.

Output: 6

Common Pitfalls

•Initialize both maxSum and currentSum to arr[0] to handle all-negative arrays correctly.

Kadane's Algorithm.java

Java

// Approach: Dynamic programming. Track max_ending_here (reset to arr[i] if negative) and max_so_far.
// Time: O(n) Space: O(1)
class Solution {

    // arr: input array
    // Function to find the sum of contiguous subarray with maximum sum.
    long maxSubarraySum(int[] arr) {
        long ans = Integer.MIN_VALUE;
        long c = 0;

        for (int val : arr) {
            c += val;
            ans = Math.max(ans, c);
            c = c < 0 ? 0 : c;
        }

        return ans;
    }
}

Was this solution helpful?