题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
1
2
3
|
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
|
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
题解
这道题依旧是动态规划，思考了一下，状态只有1个，即数组的当前长度，这样dp数组也是一维的，数组中数据的含义是以i为最后一个元素的数组的子序最大长度。
那么状态转移方程是这样的，
1
|
dp[i] = max{ dp[i - 1] + nums[i], nums[i] }
|
简单的解释是，当长度增长时，这个时候面临两种选择，一种是在之前的基础上加上当前值，一种是抛弃之前的长度，使用当前值，而当前结尾的数组的最大长度就是这两种情况的最大值。
这里依旧有个问题，即求的是数组中的子序最大值，这个最大值的子序并不一定是以当前数组的最后一个元素结尾的。所以这里还需要另外一个变量，比较判断所有元素结尾的长度中最大的那一个。
实现代码如下，算法复杂度为O(N)：
1
2
3
4
5
6
7
8
9
10
11
12
|
int maxSubArray(vector<int>& nums) {
if (nums.empty()) return 0;
int *data = new int[nums.size()];
int max_data = data[0] = nums[0];
for (int i = 1; i < nums.size(); i++) {
data[i] = max(data[i - 1] + nums[i], nums[i]);
max_data = max(data[i], max_data);
}
return max_data;
}
|
这里说下坑吧，其实关于dp数组中值得含义自己最开始并未想明白，一直认为应该是当前长度数组的最大子序和，但这样总感觉不对，实现出来的代码也是不对的，没有上面代码中的max_data = max(data[i], max_data);这一句，而最终取得结果也是dp[N - 1]，这样得到的结果并不对。
仔细想了一下，明显结果中存的不是当前数组的最大子序和，但也没想明白到底要怎么搞，最后还是偷偷看了下讨论，才最终知道要加上那一句。
另外，自己在苦苦思索过程中，还想到了另外一个复杂度很高的方法，也做个示例，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
int maxSubArray(vector<int>& nums) {
if (nums.empty()) return 0;
int **data = new int*[nums.size()];
for (int i = 0; i < nums.size(); i++) {
data[i] = new int[nums.size()];
memset(data[i], 0, sizeof(int) * nums.size());
}
int max_num = data[0][0] = nums[0];
for (int i = 1; i < nums.size(); i++) {
for (int j = 0; j <= i; j++) {
data[i][j] = data[i - 1][j] + nums[i];
max_num = max(max_num, data[i][j]);
}
}
return max_num;
}
|
这套代码算法复杂度为O(N ^ 2)，dp数组也是个二维的数组。这套代码的基本思路是这样的，以{ -2, 1, -3, 4, -1, 2, 1, -5, 4 }为例。
求值过程如下：
1
2
3
4
5
6
7
8
9
|
-2 -1 -4 0 -1 1 2 -3 1
1 -2 2 1 3 4 -1 3
-3 1 0 2 3 -2 2
4 3 5 6 1 5
-1 1 2 -3 1
2 3 -2 2
1 -4 0
-5 -1
4
|
横轴为一维，纵轴为2维。横轴每加1，当前值都把之前横轴对应的纵轴上的值都加一遍。同时另存一个变量，记录所有的最大值。这种方法整体来说复杂度太高，在leetcode中测试超时。