LeetCode Study Note | Problem 53: Maximum Subarray

Problem Overview

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

❌ My Initial Attempt (Buggy)

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, max = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, pre); // ⚠️ Incorrect
            max = Math.max(max, pre);
        }
        return max;
    }
}

Issue: This line fails to consider restarting from the current number x. It only compares cumulative values with themselves, which leads to incorrect decisions in some cases.

✅ Correct Solution: Kadane’s Algorithm

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, max = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x); // ✅ Key line
            max = Math.max(max, pre);
        }
        return max;
    }
}

🎯 Core Idea

If the previous cumulative sum (pre) is negative, it’s better to drop it and start a new subarray from the current element x.

• pre: max subarray sum ending at current index

• max: global maximum sum

• Transition formula:

pre = Math.max(pre + x, x);
max = Math.max(max, pre);

🧪 Example with All Positive Numbers

nums = [1, 2, 3, 4, 5]

Here, pre keeps growing, and the algorithm returns the sum of the whole array: 15.

🔄 Why “Restarting” Is Necessary

We compare pre + x with x:

• If pre < 0, the past is a burden → start fresh from x

• If pre >= 0, the past helps → keep accumulating

This conditional restart is what makes Kadane’s Algorithm powerful and elegant.

✨ Personal Reflection

This problem taught me how:

• Simple local greedy choices can lead to a global optimum

• Smart problem modeling simplifies dynamic programming