[toc]
题目：https://leetcode-cn.com/problems/maximum-subarray/
1.暴力法
///
/// Author: liyanjun
/// description: 暴力法
///
int maxSubArray(List<int> nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int maxNumber = nums.first;
for (var begin = 0; begin < nums.length; begin++) {
for (var end = begin + 1; end < nums.length; end++) {
int sum = 0;
for (var i = begin; i <= end; i++) {
sum += nums[i];
}
maxNumber = max(sum, maxNumber);
}
}
return maxNumber;
}
空间复杂度：O(1)，时间复杂度：
1.1 暴力法优化
重复利用前面计算过的结果
// ◼ 重复利用前面计算过的结果
int maxSubArray1(List<int> nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int maxNumber = nums.first;
for (var begin = 0; begin < nums.length; begin++) {
int sum = 0;
for (var end = begin; end < nums.length; end++) {
sum +=nums[end];
maxNumber = max(sum, maxNumber);
}
}
return maxNumber;
}
}
空间复杂度：O(1)，时间复杂度：
2.分治法
将序列均匀地分割成 2 个子序列
- [begin , end) = [begin , mid) + [mid , end)，mid = (begin + end) >> 1
假设 [begin , end) 的最大连续子序列和是 S[i , j) ，那么它有 3 种可能
- [i , j) 存在于 [begin , mid) 中，同时 S[i , j) 也是 [begin , mid) 的最大连续子序列和
- [i , j) 存在于 [mid , end) 中，同时 S[i , j) 也是 [mid , end) 的最大连续子序列和
- [i , j) 一部分存在于 [begin , mid) 中，另一部分存在于 [mid , end) 中
- [i , j) = [i , mid) + [mid , j)
- S[i , mid) = max { S[k , mid) }，begin ≤ k ＜ mid
- S[mid , j) = max { S[mid , k) }，mid ＜ k ≤ end
代码
///
/// Author: liyanjun
/// description: [begin]到[end]连续子序列的和 左闭右开
///
int divideConquer(List<int> nums, int begin, int end) {
if (end - begin < 2) return nums[begin];
int mid = (end + begin) >> 1;
int leftMax = nums[mid - 1];
//计算从mid-1开始往左遍历 最大值
int leftSum = leftMax;
for (int i = mid - 2; i >= begin; i--) {
leftSum += nums[i];
leftMax = max(leftMax, leftSum);
}
//计算从mid开始开始往右遍历 最大值
int rightMax = nums[mid];
int rightSum = rightMax;
for (int i = mid + 1; i < end; i++) {
rightSum += nums[i];
rightMax = max(rightMax, rightSum);
}
return max(
leftMax + rightMax, //横跨左右两边的最大子序列和
max(
divideConquer(nums, begin, mid), //左边最大子序列和
divideConquer(nums, mid, end))); //右边最大子序列和
}
}
空间复杂度：O(logn)，
时间复杂度$T(n)=2T(n/2)+O(n) = O(n*logn)
3.动态规划
状态定义：
假设 dp(i) 是以 nums[i] 结尾的最大连续子序列和（nums是整个序列）
- 以 nums[0] –2 结尾的最大连续子序列是 –2，所以 dp(0) = –2
- 以 nums[1] 1 结尾的最大连续子序列是 1，所以 dp(1) = 1
- 以 nums[2] –3 结尾的最大连续子序列是 1、–3，所以 dp(2) = dp(1) + (–3) = –2
- 以 nums[3] 4 结尾的最大连续子序列是 4，所以 dp(3) = 4
- 以 nums[4] –1 结尾的最大连续子序列是 4、–1，所以 dp(4) = dp(3) + (–1) = 3
- 以 nums[5] 2 结尾的最大连续子序列是 4、–1、2，所以 dp(5) = dp(4) + 2 = 5
- 以 nums[6] 1 结尾的最大连续子序列是 4、–1、2、1，所以 dp(6) = dp(5) + 1 = 6
- 以 nums[7] –5 结尾的最大连续子序列是 4、–1、2、1、–5，所以 dp(7) = dp(6) + (–5) = 1
- 以 nums[8] 4 结尾的最大连续子序列是 4、–1、2、1、–5、4，所以 dp(8) = dp(7) + 4 = 5
状态转移方程：
- 如果 dp(i – 1) ≤ 0，那么 dp(i) = nums[i]
- 如果 dp(i – 1) > 0，那么 dp(i) = dp(i – 1) + nums[i]
初始状态
- dp(0) 的值是 nums[0]
最终的解
- 最大连续子序列和是所有 dp(i) 中的最大值 max { dp(i) }，i ∈ [0, nums.length)
代码
int maxSubArray3(List<int> nums) {
if (nums == null || nums.length == 0) {
return 0;
}
List<int> dp = List(nums.length);
dp[0] = nums[0];
int maxDp = dp[0];
for (var i = 1; i < nums.length; i++) {
if (dp[i - 1] <= 0) {
dp[i] = nums[i];
} else {
dp[i] = dp[i - 1] + nums[i];
}
maxDp = max(maxDp, dp[i]);
}
return maxDp;
}
3.1 动态规划优化
优化空间，不需要数组
///
/// Author: liyanjun
/// description: 动态规划优化
/// 优化空间
///
int maxSubArray4(List<int> nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int dp = nums[0];
int maxDp =dp;
for (var i = 1; i < nums.length; i++) {
if (dp <= 0) {
dp = nums[i];
} else {
dp = dp + nums[i];
}
maxDp = max(maxDp, dp);
}
return maxDp;
}
