Skip to content

53. Maximum Subarray

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

Intuition

Approach

Complexity

  • Time complexity:
  • Space complexity:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int max = nums[0];
        res[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (res[i - 1] < 0) {
                res[i] = nums[i];
            } else {
                res[i] = res[i - 1] + nums[i];
            }
            max = Math.max(max, res[i]);
        }
        return max;
    }
}