网博士自助建站系统,游戏网页设计图片,住房和城乡建设部网站证书查询,互联网保险的风险/** 53.Maximum Subarray * 2016-5-7 by Mingyang * 如果我们从头遍历这个数组。对于数组中的其中一个元素#xff0c;它只有两个选择#xff1a; 1.* 要么加入之前的数组加和之中#xff08;跟别人一组#xff09; * 2. 要么自己单立一个数组#xff08;自己单开一组它只有两个选择 1.* 要么加入之前的数组加和之中跟别人一组 * 2. 要么自己单立一个数组自己单开一组* 所以对于这个元素应该如何选择就看他能对哪个组的贡献大。如果跟别人一组* 能让总加和变大还是跟别人一组好了如果自己起个头一组自己的值比之前加和的值还要大那么还是自己单开一组好了。* 所以利用一个dp数组记录每一轮sum的最大值dp[i]表示当前这个元素是跟之前数组加和一组还是自己单立一组好然后维护一个全局最大值即位答案* 那么这道题目开始想能不能用maxSubArray(int A[], int i, int j), which means the maxSubArray for A[i: j].* 但是这么写子函数就很难找到这种关系。那么我们接下来就怎么做呢* maxSubArray(int A[], int i), which means the maxSubArray for A[0:i ] which must has A[i] as the end element.* 那么就下来的关系就是* dp[i] Math.max(A[i], dp[i - 1] A[i]);* 也就是说对于A[i]到底加不加进来我们只需要看这个加进来大还是单独大。* 因为你如果加进来都比单独大那么后面还是一个增量。* 千万不要写成dp[i] Math.max(dp[i-1], dp[i - 1] A[i]); * Kadans algorithm O(n) time and O(1) space */public static int maxSubArray(int[] A) {int[] dp new int[A.length];int max A[0];dp[0] A[0];for (int i 1; i A.length; i) {dp[i] Math.max(A[i], dp[i - 1] A[i]); // 这里只比较了自己另外开一个和原来的加一起开的区别max Math.max(max, dp[i]);} //不是每一个dp都是返回最后一个dp值哦有可能返回全局变量return max;}/** 下面是我自己的解法开始想的有点复杂然后后面仔细列举一下也是蛮简单的这里用了一个dp数组* dp[i]表示包括i在内的连续数组的最大值而不是到i最优的结果* [-1,-2]那么dp[1]-3,因为要把-2包括进来* 那么如果每个数自己就很大比加起前面累积的dp还大那么久自成一家* 否则的话需要加起来每次更新dp的时候与全局变量max比较一下*/public int maxSubArray1(int[] nums) {int lennums.length;int maxnums[0];int[] dpnew int[len];dp[0]nums[0];for(int i1;ilen;i){if(nums[i]nums[i]dp[i-1]){dp[i]nums[i];maxMath.max(max,dp[i]);}else{dp[i]dp[i-1]nums[i];maxMath.max(max,dp[i]);}}return max;} 转载于:https://www.cnblogs.com/zmyvszk/p/5469683.html
