网站建设如何财务处理,网站建立的,phpcms对比wordpress,做的比较好的手机网站题意理解#xff1a; 给定一个数列#xff0c;求连续的子序列的和最大可以是多少#xff1f; 子数组 是数组中的一个连续部分。 比如#xff1a; nums [-2,1,-3,4,-1,2,1,-5,4] 最大子序列的和#xff1a;6#xff08;4-121#xff09; 解题思路#xff1a; 使用贪心的… 题意理解 给定一个数列求连续的子序列的和最大可以是多少 子数组 是数组中的一个连续部分。 比如 nums [-2,1,-3,4,-1,2,1,-5,4] 最大子序列的和64-121 解题思路 使用贪心的思路来解题则需要定义局部最优解和全局最优解及分析之间的关系。 当遍历到第i个元素时当前子序列和为负数时与其继续累加子序列的值不如设其之前的子序列。 因为负数之后拖累子序列和 所以我们需要再合适的地方舍弃子序列和为负的子序列——即合适的位置开启一个结果可能为正的子序列。 又因为我们要求一个最大的子序列和 所以我们需要一个值来记录最大子序列和其总揭露最大子序列和和当前子序列和的最大值。 最终我们能得到连续子序列的最大值。 1.贪心解题
我们使用result来记录最大子序列和curSum来记录当前子序列和。
注意 当且仅当数组只有一个元素时则最大子序列和即为这个元素即使这个元素可能时负数。 如果一个序列的元素全为负数的话其最大子序列和为该序列中最大的负数因为其和任何一个负数相加都会变得更小。
所以result和curSum从nums[0]初始化遍历应从i1处开始。 当只有一个元素时返回当前值 curSum为负子序列和总是从0累加当前值。
public int maxSubArray(int[] nums) {int resultnums[0];int curSumnums[0];for(int i1;inums.length;i){curSumMath.max(curSum,0);//不从负数累加curSumnums[i];resultMath.max(curSum,result);}return result;}
2.分析 时间复杂度O(n) 空间复杂度O(n)
