publicclassSolution { /** * @param nums: a list of integers * @return: A integer indicate the sum of minimum subarray */publicintminSubArray(ArrayList<Integer> nums) {// write your codeint max =0, min =Integer.MAX_VALUE;int prefixSum =0;for(int i =0; i <nums.size(); i++){ prefixSum +=nums.get(i); min =Math.min(min, prefixSum - max); max =Math.max(max, prefixSum); }return min; }}
可以看到,在 kadane's algorithm 中,我们保存的这个 prevMin 始终是连续的,起点不一定是哪,但是终点一定是 current,是一个 local 最优解。我们每次迭代,用 local 最优解去更新 global 最优解。
publicclassSolution { /** * @param nums: a list of integers * @return: A integer indicate the sum of minimum subarray */publicintminSubArray(ArrayList<Integer> nums) {// write your codeint prevMin =0;int cur =nums.get(0);int minRst =nums.get(0);for(int i =1; i <nums.size(); i++){ cur =Math.min(nums.get(i), prevMin +nums.get(i)); minRst =Math.min(minRst, cur); prevMin = cur; }return minRst; }}
publicclassSolution {publicintmaxSubArray(int[] nums) {if(nums ==null||nums.length==0) return0;int max =Integer.MIN_VALUE, min =0;int prefixSum =0;for(int i =0; i <nums.length; i++){ prefixSum += nums[i]; max =Math.max(max, prefixSum - min); min =Math.min(min, prefixSum); }return max; }}
用 Kadane's Algorithm:
publicclassSolution {publicintmaxSubArray(int[] nums) {if(nums ==null||nums.length==0) return0;int cur = nums[0];int max = nums[0];for(int i =1; i <nums.length; i++){ cur =Math.max(nums[i], cur + nums[i]); max =Math.max(max, cur); }return max; }}
负号。遇到负号时,原本的 min / max 会直接反转。最优解可能是有一系列正数相乘而来,但也可能是一系列正数中带着偶数个数的负数。
保存以当前元素截止的 min / max subarray (保证连续性),遇到负数时调换相乘。
加法操作遇到 0 是无所谓的,乘法操作却会导致直接切断 prefix product.
每个位置的 max / min subarray 同时考虑当前元素,正确处理 0 之余保证连续性。
其实这个做法与其说像 prefix product ,不如说更像 Kadane's Algorithm. 可以看到这个算法可以有效免疫各种切断的情况,只维护到当前位置结尾的 max / min subarray 结果就可以了。
在这里面,min/max 是连续的,local 以 i 结尾的; rst 是 global 非连续的。
前缀积在这题上没用,所有的都是 localMin / localMax,迭代更新。
不能用 val = 1 来做初始化,要用 nums[0];
nums[i] 为负时,要多开个临时变量,不然会覆盖掉下一行需要的值
publicclassSolution {publicintmaxProduct(int[] nums) {int max = nums[0], min = nums[0];int rst = nums[0];for(int i =1; i <nums.length; i++){if(nums[i] >0){ max =Math.max(nums[i], max * nums[i]); min =Math.min(nums[i], min * nums[i]); } else {int oldMax = max; max =Math.max(nums[i], min * nums[i]); min =Math.min(nums[i], oldMax * nums[i]); } rst =Math.max(rst, max); }return rst; }}
Subarray I 只是开胃菜的话,这道题就开始比较认真考察如何利用 prefix sum 做 DP 解决 subarray sum 类问题了。
这次光用 local 变量更新然后返回 global 最优还不够,我们需要保存对于每一个子问题的 global 最优(可能并不以当前位置结尾),用于后面的左右两边全局查询。
我们需要利用 prefix sum 数组,定义两个 dp[]
left[i] 代表从最左边到 i 位置所能取得的最大 subarray sum;
right[i] 代表从最右边到 i 位置所能取得的最大 subarray sum;
两个数组都是 global 解。
每次迭代的变量 minSum 和 prefixSum 是相对于每个位置的 local 解。
这样对于每一个位置 i ,我们都可以用 left[] 和 right[] 的子数组把最优解拼接出来。
publicclassSolution { /** * @param nums: A list of integers * @return: An integer denotes the sum of max two non-overlapping subarrays */publicintmaxTwoSubArrays(ArrayList<Integer> nums) {// write your codeif(nums ==null||nums.size() ==0) return0;int n =nums.size();// Maximum subarray value from left/right with n elementsint[] left =newint[n];int[] right =newint[n];int prefixSum =0;int minSum =0;int max =Integer.MIN_VALUE;for(int i =0; i < n; i++){ prefixSum +=nums.get(i); max =Math.max(max, prefixSum - minSum); minSum =Math.min(minSum, prefixSum); left[i] = max; } prefixSum =0; minSum =0; max =Integer.MIN_VALUE;for(int i = n -1; i >=0; i--){ prefixSum +=nums.get(i); max =Math.max(max, prefixSum - minSum); minSum =Math.min(minSum, prefixSum); right[i] = max; }int rst =Integer.MIN_VALUE;for(int i =0; i < n -1; i++){ rst =Math.max(rst, left[i] + right[i +1]); }return rst; }}
publicclassSolution { /** * @param nums: A list of integers * @return: An integer denotes the sum of max two non-overlapping subarrays */publicintmaxTwoSubArrays(ArrayList<Integer> nums) {// write your codeif(nums ==null||nums.size() ==0) return0;int n =nums.size();// Maximum subarray value from left/right with n elementsint[] left =newint[n];int[] right =newint[n];int prevMax =nums.get(0);int max =nums.get(0); left[0] =nums.get(0);for(int i =1; i < n; i++){ prevMax =Math.max(nums.get(i),nums.get(i) + prevMax); max =Math.max(max, prevMax); left[i] = max; } prevMax =nums.get(n -1); max =nums.get(n -1); right[n -1] =nums.get(n -1);for(int i = n -2; i >=0; i--){ prevMax =Math.max(nums.get(i),nums.get(i) + prevMax); max =Math.max(max, prevMax); right[i] = max; }int rst =Integer.MIN_VALUE;for(int i =0; i < n -1; i++){ rst =Math.max(rst, left[i] + right[i +1]); }return rst; }}