网站开发pmp,如何做二级域名子目录网站,六安人论坛招聘网,flash 网站源码#x1f468;#x1f3eb; 题目地址 无后效性
为了保证计算子问题能够按照顺序、不重复地进行#xff0c;动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。换言之#xff0c;动态规划对状态空间的遍历构成一张有向无环图#xff0c;遍… 题目地址 无后效性
为了保证计算子问题能够按照顺序、不重复地进行动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。换言之动态规划对状态空间的遍历构成一张有向无环图遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的「状态」图中的边则对应状态之间的「转移」转移的选取就是动态规划中的「决策」。
关键 1理解题意
题目要我们找出和最大的连续子数组的值是多少「连续」是关键字连续很重要不是子序列。
题目只要求返回结果不要求得到最大的连续子数组是哪一个。这样的问题通常可以使用「动态规划」解决。
关键 2如何定义子问题如何定义状态
设计状态思路把不确定的因素确定下来进而把子问题定义清楚把子问题定义得简单。动态规划的思想通过解决了一个一个简单的问题进而把简单的问题的解组成了复杂的问题的解。 DP
public class Solution {public int maxSubArray(int[] nums) {int n nums.length;int[] f new int[n];// 记录nums[i]结尾的最大连续数组和f[0] nums[0];int ans f[0];for (int i 1; i n; i){f[i] Math.max(f[i - 1] nums[i], nums[i]);ans Math.max(ans, f[i]);}return ans;}
} DP优化空间
public class Solution {public int maxSubArray(int[] nums) {int pre 0;int res nums[0];for (int num : nums) {pre Math.max(pre num, num);res Math.max(res, pre);}return res;}
} 分治
public class Solution {public int maxSubArray(int[] nums) {int len nums.length;if (len 0) {return 0;}return maxSubArraySum(nums, 0, len - 1);}private int maxCrossingSum(int[] nums, int left, int mid, int right) {// 一定会包含 nums[mid] 这个元素int sum 0;int leftSum Integer.MIN_VALUE;// 左半边包含 nums[mid] 元素最多可以到什么地方// 走到最边界看看最值是什么// 计算以 mid 结尾的最大的子数组的和for (int i mid; i left; i--) {sum nums[i];if (sum leftSum) {leftSum sum;}}sum 0;int rightSum Integer.MIN_VALUE;// 右半边不包含 nums[mid] 元素最多可以到什么地方// 计算以 mid1 开始的最大的子数组的和for (int i mid 1; i right; i) {sum nums[i];if (sum rightSum) {rightSum sum;}}return leftSum rightSum;}private int maxSubArraySum(int[] nums, int left, int right) {if (left right) {return nums[left];}int mid left (right - left) / 2;return max3(maxSubArraySum(nums, left, mid),maxSubArraySum(nums, mid 1, right),maxCrossingSum(nums, left, mid, right));}private int max3(int num1, int num2, int num3) {return Math.max(num1, Math.max(num2, num3));}
} 参考地址
