leetcode53: 最大字数组和

leetcode53: 最大字数组和

动态规划

动态规划：定义一个长度比传入数组大一的数组
//    将初值设为nums[0]
//    定义一个max为nums[0]（假设第一个元素最大）
//    遍历传入数组，取nums[n]+dp[n-1]和 nums[n]的最大值赋给dp[n]，若max小于dp[n]说明这个num[n]对结果有增益
//    若max>dp[n]，说明这个nums[n]对结果有负增益，舍掉
    public static int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i- 1] + nums[i], nums[i]);
            if (max < dp[i]) {
                max = dp[i];
            }
        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

贪心算法

//    贪心, 若sum>0，则继续累加将会对结果增益，保留结果并加上本次遍历的元素；若sum<0，则对结果有负增益，舍弃
//    只要sum比0大，就一直累加
    public static int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for(int num : nums) {
            if(sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15