53. 最大子数组和

53. 最大子数组和

动态规划

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];  // dp[i] 表示以nums[i]为结尾的子数组的最大和
        dp[0] = nums[0];
        int res = dp[0];

        for(int i = 1; i < n; i++){
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

动态规划——压缩空间

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int pre = nums[0];
        int res = pre;

        for(int i = 1; i < n; i++){
            pre = Math.max(pre + nums[i], nums[i]);
            res = Math.max(res, pre);
        }

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

贪心

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int sum = nums[0];
        int res = nums[0];

        for(int i = 1; i < n; i++){
            if(sum > 0) sum += nums[i];
            else sum = nums[i];
            res = Math.max(res, sum);
        }

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int sum = 0;
        int res = Integer.MIN_VALUE;

        for(int i = 0; i < n; i++){
            sum += nums[i];
            res = Math.max(res, sum);
            if(sum < 0) sum = 0;
        }

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int sum = 0;
        int res = nums[0];

        for(int i = 0; i < n; i++){
            sum += nums[i];
            res = Math.max(res, sum);
            if(sum < 0) sum = 0;
        }

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int sum = nums[0];
        int res = nums[0];

        for(int i = 1; i < n; i++){
            if(sum < 0) sum = 0;
            sum += nums[i];
            res = Math.max(res, sum);
        }

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15