动态规划攻略之：连续数列

动态规划攻略之：连续数列

题目

给定一个整数数组，找出总和最大的连续数列，并返回总和。

示例：

输入： [-2,1,-3,4,-1,2,1,-5,4]输出： 6解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。

解题思路

根据题意，我妈可以通过动态规划的思路来解答此题。

假设 nums 数组的长度为 n, 下标从 0 到 n - 1; 我们用 f(i) 代表以第 i 个数结尾的连续子数组的最大和。

所以，我们只需要求出每个位置的 f(i)，然后返回 f 数组中的最大值即可。

如何求 f(i) 呢？我们可以通过比较 nums[i] 和 f(i-1) + nums[i] 的大小，来获得一个比较大的值，于是动态规划转移方程为：

f(i) = max{f(i-1) + nums[i], nums[i]}

代码实现如下。

代码实现

class Solution { public int maxSubArray(int[] nums) { int pre = 0, maxAns = nums[0]; for (int i = 0; i < nums.length; i++){ pre = Math.max(pre + nums[i], nums[i]); maxAns = Math.max(maxAns, pre); } return

最后

时间复杂度：O(n)空间复杂度：O(n)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。