dp第五天

进度有些落后了。。

「动态规划」 – 学习计划 – 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

53. 最大子数组和

这题是简单常数级别的dp，比打家劫舍还低一级，一下没反应过来。。

/**
 53. 最大子数组和
 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

 子数组 是数组中的一个连续部分。



 示例 1：

 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 输出：6
 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 示例 2：

 输入：nums = [1]
 输出：1
 示例 3：

 输入：nums = [5,4,-1,7,8]
 输出：23


 提示：

 1 <= nums.length <= 10^5
 -10^4 <= nums[i] <= 10^4


 * @author zeroheart
 *
 */
public class Question53 {

    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int max = nums[0];
        int pre = 0;
        for(int i = 0; i<len; i++){
            // 方程要考虑好，这个是常数级别的dp, pre = Math.max(nums[i], pre+nums[i]); 不是数组级别的dp[]，不同于简单版本的打家劫舍
            pre = Math.max(nums[i], pre+nums[i]);
            max = Math.max(pre, max);
        }
        return max;
    }

    public static void main(String[] args) {

    }
}

918. 环形子数组的最大和

这题需要技巧，分两种情况，一种是上面题目的例子，一种情况是成环了，需要使用total-min来算最大，同时考虑max<=0的话，数组都是负数，total==min，返回max即可。

/**
 918. 环形子数组的最大和
 给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

 环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

 子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。



 示例 1：

 输入：nums = [1,-2,3,-2]
 输出：3
 解释：从子数组 [3] 得到最大和 3
 示例 2：

 输入：nums = [5,-3,5]
 输出：10
 解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
 示例 3：

 输入：nums = [3,-2,2,-3]
 输出：3
 解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3


 提示：

 n == nums.length
 1 <= n <= 3 * 104
 -3 * 10^4 <= nums[i] <= 3 * 10^4

 * @author zeroheart
 *
 */
public class Question918 {

    public int maxSubarraySumCircular(int[] nums) {
        // 这样写的问题是可能取到两次首位的数字
//        int len = nums.length * 2 -1;
//        int pre = 0;
//        int max = nums[0];
//        for(int i = 0; i<len; i++){
//            int x = i % nums.length;
//            pre = Math.max(nums[x], pre + nums[x]);
//            max = Math.max(max, pre);
//        }
//        return max;



        // 这题的技巧是，不成环最大的 和 所有数字只和-不成环最小的 比大小

        int len = nums.length;
        int pre = 0;
        int max = nums[0];
        int minPre = 0;
        int min = nums[0];
        int total = 0;
        for(int i = 0; i<len; i++){
            pre = Math.max(nums[i], pre + nums[i]);
            max = Math.max(max, pre);

            minPre = Math.min(nums[i], minPre + nums[i]);
            min = Math.min(min, minPre);

            total += nums[i];
        }

        // 最后还有一点处理，max<=0的话直接返回max，因为total==min，total-min = 0
        return max > 0 ? Math.max(max, total - min) : max;

    }

    public static void main(String[] args) {

    }
}