网站建设实训总结2000字/网络营销的概念和特征

题目
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例:

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

思路

这题其实就是求最大子序和

方法1（暴力法）

• 枚举起点和终点，时间复杂度O(n^2)
• 此处有一些小优化，如果是负数，那么就不要设为起点或者终点了

方法2（动态规划）

• max_sum(i)代表假设第i个元素被选择的话，那么从最开始到第i个元素，且第i个元素被累加进来，它的最大连续子序列和

a. 分治子问题第i-1元素可以选择或者不选择，不选择的话就是0max_sum(i) = Max(max_sum(i - 1),0) + a[i]
b. 状态数组定义f[i] 
c. DP方程f[i] = Max(f[i-1], 0) + a[i]

也可以换一种思考方式

我们不断地用一个sum进行累加，如果累加到一个地方为负数了，那就丢掉，直到每一步都找到一个最大值

dp[i] = max(nums[i], num[i] + dp[i - 1])

	public int maxSubArray(int[] nums) {int[] dp = nums;int max = nums[0];for (int i = 1; i < nums.length; i++) {dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
//      dp[i] = nums[i] + Math.max(0, dp[i-1]);max = Math.max(dp[i], max);}return max;}

复杂度分析

• 时间复杂度：O(n)
  • 其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
• 空间复杂度：O(1)
  • 我们只需要常数空间存放若干变量（这里O(1)是指不另外开辟dp数组，而是直接拿nums来进行运算）