Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

问题描述

给定一个整数数组，返回最大的子数组的和。

样例

**输入**：[-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出：6
解释：子数组 [4, -1, 2, 1] 有最大的和 6

解法 1

题目要求计算子数组的和的最大值，我们可以把这个问题分为两部分:

1. 计算以第 i 个元素为末尾的子数组的和的最大值
2. 计算 1 中计算出来的 n 个最大值中的最大

我们用一个数组 dp 来保留中间结果，dp[i] 表示数组中以第 i+1 个元素为末尾的子数组的和的最大值。则最终返回 dp 数组中的最大值即可。

显然 dp[0] = nums[0]，现在考虑如何计算 dp[i]，这时，仅包括两种可能情形:

• 该子数组包含第 i 个元素，此时这样的子数组的和最大为 dp[i-1]+nums[i-1]
• 该子数组不包含第 i 个元素，此时这样的子数组仅有 [nums[i-1]]

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

这样我们仅需一次循环，即可计算出所有 dp 数组的所有值，并在循环的过程中，计算出 dp 数组的最大值即为最终的结果。