开发一款app大概多少钱,梁水才seo优化专家,宁波发布最新通报,年收入100万要交多少税文章目录 连续子数组的最大和题目思路代码实现 连续子数组的最大和(二)题目思路代码实现 连续子数组的最大和
题目
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。
子数组… 文章目录 连续子数组的最大和题目思路代码实现 连续子数组的最大和(二)题目思路代码实现 连续子数组的最大和
题目
给你一个整数数组 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 LeetCode链接
思路
以nums [-2,1,-3,4,-1,2,1,-5,4]数据为例 采用动态规划的思想将以上问题转化为如下子问题
求以-2结尾的连续子数组的最大值求以1结尾的连续子数据的最大值求以-3结尾的连续子数组的最大值求以4结尾的连续子数组的最大值求以-1结尾的连续子数组的最大值求以2结尾的连续子数组的最大值求以1结尾的连续子数组的最大值求以-5结尾的连续子数组的最大值求以4结尾的连续子数组的最大值 然后求以上子问题的最大值即为所得结果
我们这里再求子问题2求以1结尾的连续子数据的最大值 那对应的子数组只有2组分别为[-2,1]和[1]很明显最大值数组为后者那对应到公式应该为 Math.max(prev num[i],num[i]),其中prev表示以-2结尾的连续子数组的最大值num[i]对应当前下标值 更加详细讲解可参考LeetCode 经典动态规划问题
代码实现 public int maxSubArray(int[] nums) {if(nums null || nums.length 0){return 0;}int prev 0;int result nums[0];for(int num:nums){prev Math.max(prev num,num);result Math.max(prev,result);}return result;}连续子数组的最大和(二)
题目
描述 输入一个长度为n的整型数组array数组中的一个或连续多个整数组成一个子数组找到一个具有最大和的连续子数组。 1.子数组是连续的比如[1,3,5,7,9]的子数组有[1,3][3,5,7]等等但是[1,3,7]不是子数组 2.如果存在多个最大和的连续子数组那么返回其中长度最长的该题数据保证这个最长的只存在一个 3.该题定义的子数组的最小长度为1不存在为空的子数组即不存在[]是某个数组的子数组 4.返回的数组不计入空间复杂度计算
示例1 输入 [1,-2,3,10,-4,7,2,-5] 返回值 [3,10,-4,7,2] 说明 经分析可知输入数组的子数组[3,10,-4,7,2]可以求得最大和为18故返回[3,10,-4,7,2]
示例2 输入 [1] 返回值 [1]
示例3 输入 [1,2,-3,4,-1,1,-3,2] 返回值 [1,2,-3,4,-1,1] 说明 经分析可知最大子数组的和为4有[4],[4,-1,1],[1,2,-3,4],[1,2,-3,4,-1,1]故返回其中长度最长的[1,2,-3,4,-1,1]
思路
和上题整体思路一致只不过需要在计算子问题的过程中把子问题解对应的数组开始下标和结束下标记录下来
代码实现
public int[] FindGreatestSumOfSubArray (int[] array) {if(array null || array.length 0){return new int[0];}int[] dp new int[array.length];dp[0] array[0];int max dp[0];//start end表示所求数组开始与结束下标int start 0;int end 1;//当前一个子问题的最大值小于0时需要重置开始位置负责记录开始问题int temp 0;for(int i 1;iarray.length;i){if(dp[i-1] 0){dp[i] array[i];temp i;}else{dp[i] dp[i-1]array[i];}if(dp[i] max){max dp[i];start temp;end i1;}}return Arrays.copyOfRange(array,start,end);}
