04-Maximum-Subarray.md

Maximum Subarray

Problem Link

https://leetcode.com/problems/maximum-subarray/

---

Pattern

• Kadane Algorithm

---

Approach

Use Kadane's algorithm: track current sum (max ending here) and global max. Reset current sum to nums[i] if current sum is negative.

---

Time Complexity

O(n)

Space Complexity

O(1)

---

Java Solution

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSoFar = nums[0];
        int curr = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curr = Math.max(nums[i], curr + nums[i]);
            maxSoFar = Math.max(maxSoFar, curr);
        }
        return maxSoFar;
    }
}