重复建设政务网站,黑白网站设计,英文站用wordpress,成都企业排名给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。 子数组 是数组中的一个连续部分。 输入#xff1a;nums [-2,1,-3,4,-1,2,1,-5,4]
输出#xff1a;6
解释#xff1a;连续… 给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。 子数组 是数组中的一个连续部分。 输入nums [-2,1,-3,4,-1,2,1,-5,4]
输出6
解释连续子数组 [4,-1,2,1] 的和最大为 6 。 最大子数组和我们今天从递推——记忆化搜索——动态规划来解决本题
递推 假如当前数为1如果前面的sum和是小于0的是不是有 数组[-2,1]的子数组和一定比[1]的子数组和小所以我们就可以推得递推假如你当前元素前面的子数组和是小于零的加上当前的值的和一定比当前元素本身的值要小所以我们取最大的只取本身这个元素所以我们就可以推得关系式
Math.max(nums[i],前面子数组最大和nums[i]);
函数签名 public int dfs(int i,int[] nums){} 函数dfs返回的是当包含索引为i的元素时子数组的最大和通过for循环将0~n-1索引的最大子数组和通过比较找出最大值就是我们所要的结果 int ansnums[0];for(int i1;inums.length;i){ansMath.max(ans,dfs(i,nums));} 递归很明显 因为中间做了很多重复的操作使得超时那么我们怎么样才能避免这样重复的操作发生呢
这个时候我们的记忆化搜索就派上了用场
记忆化搜索 记忆化搜索无非就是维护一个数组将计算后的结果存进数组中等到计算时先去数组中找看是否被计算过如果计算过直接在数组中找如果没有计算计算之后将结果存进数组中以便后续的使用
int[] memo;memonew int[nums.length];Arrays.fill(memo,-1); if(memo[i]!-1){return memo[i];}memo[i]Math.max(nums[i],dfs(i-1,nums)nums[i]); 源码如下 int[] memo;public int maxSubArray(int[] nums) {if(numsnull||nums.length0){return 0;}memonew int[nums.length];Arrays.fill(memo,-1);int ansnums[0];for(int i1;inums.length;i){ansMath.max(ans,dfs(i,nums));}return ans;}public int dfs(int i,int[] nums){if(i0){return 0;}if(memo[i]!-1){return memo[i];}memo[i]Math.max(nums[i],dfs(i-1,nums)nums[i]);return memo[i];}
动态规划 递归是自顶向下那么动态规划就是自底向上通过基础base推这里有个非常高大上的名字就做状态转移方程其实
Math.max(nums[i],dfs(i-1,nums)nums[i]);
其实递推关系式和我们的状态转移方程在某种意义上来讲是一样的
int[] dpnew int[nums.length];
base(当dp[0]时只有索引为0的元素自然而然最大值就是nums[0])
dp[0]nums[0];
进行状态转移
for(int i1;inums.length;i){dp[i]Math.max(nums[i],dp[i-1]nums[i]);}
源码如下 //动态规划public int maxSubArray(int[] nums) {if(numsnull||nums.length0){return 0;}int[] dpnew int[nums.length];dp[0]nums[0];for(int i1;inums.length;i){dp[i]Math.max(nums[i],dp[i-1]nums[i]);}int ansInteger.MIN_VALUE;for(int i0;idp.length;i){ansMath.max(dp[i],ans); }return ans;} 在这里给大家安利一种比较简便的方法不用你会动态规划、不用你会记忆化搜素、不用你会递归 所谓的正反馈法
假如现在的一个 假如当前你准备要往子数组[-2,1,-3]中加入元素4但是原本这个子数组的值是小于0如果你是这个4本身自身已经很大了在这个弱肉强食的时代你还要带几个拖油瓶去拉低你自己的值即使没有神一样的队友也解决不要猪一样的队友所以不如自己单干正向反馈类似于这个思想
源代码如下
public int maxSubArray(int[] nums) {if(numsnull||nums.length0){return 0;}//正反馈int sum0;int ansnums[0];for(int num:nums){//如果之前的和大于0说明之前的操作对于结果是正反馈if(sum0){sumnum;//之前的和小于0说明之前的操作对于当前结果是负反馈}else{sumnum;}//去中间最大值ansMath.max(sum,ans);}return ans;}
