[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;
}
空間復(fù)雜度：O(1)褪猛，時(shí)間復(fù)雜度：
1.1 暴力法優(yōu)化
重復(fù)利用前面計(jì)算過(guò)的結(jié)果
// ? 重復(fù)利用前面計(jì)算過(guò)的結(jié)果
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;
}
}
空間復(fù)雜度：O(1)，時(shí)間復(fù)雜度：
2.分治法
將序列均勻地分割成 2 個(gè)子序列
- [begin , end) = [begin , mid) + [mid , end)，mid = (begin + end) >> 1
假設(shè) [begin , end) 的最大連續(xù)子序列和是 S[i , j) 猜惋，那么它有 3 種可能
- [i , j) 存在于 [begin , mid) 中尽狠，同時(shí) S[i , j) 也是 [begin , mid) 的最大連續(xù)子序列和
- [i , j) 存在于 [mid , end) 中署驻，同時(shí) S[i , j) 也是 [mid , end) 的最大連續(xù)子序列和
- [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]連續(xù)子序列的和 左閉右開
///
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];
//計(jì)算從mid-1開始往左遍歷 最大值
int leftSum = leftMax;
for (int i = mid - 2; i >= begin; i--) {
leftSum += nums[i];
leftMax = max(leftMax, leftSum);
}
//計(jì)算從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))); //右邊最大子序列和
}
}
空間復(fù)雜度：O(logn)庐杨，
時(shí)間復(fù)雜度$T(n)=2T(n/2)+O(n) = O(n*logn)
3.動(dòng)態(tài)規(guī)劃
狀態(tài)定義：
假設(shè) dp(i) 是以 nums[i] 結(jié)尾的最大連續(xù)子序列和（nums是整個(gè)序列）
- 以 nums[0] –2 結(jié)尾的最大連續(xù)子序列是 –2，所以 dp(0) = –2
- 以 nums[1] 1 結(jié)尾的最大連續(xù)子序列是 1夹供，所以 dp(1) = 1
- 以 nums[2] –3 結(jié)尾的最大連續(xù)子序列是 1灵份、–3，所以 dp(2) = dp(1) + (–3) = –2
- 以 nums[3] 4 結(jié)尾的最大連續(xù)子序列是 4哮洽，所以 dp(3) = 4
- 以 nums[4] –1 結(jié)尾的最大連續(xù)子序列是 4填渠、–1，所以 dp(4) = dp(3) + (–1) = 3
- 以 nums[5] 2 結(jié)尾的最大連續(xù)子序列是 4鸟辅、–1氛什、2，所以 dp(5) = dp(4) + 2 = 5
- 以 nums[6] 1 結(jié)尾的最大連續(xù)子序列是 4匪凉、–1枪眉、2、1再层，所以 dp(6) = dp(5) + 1 = 6
- 以 nums[7] –5 結(jié)尾的最大連續(xù)子序列是 4贸铜、–1堡纬、2、1蒿秦、–5烤镐，所以 dp(7) = dp(6) + (–5) = 1
- 以 nums[8] 4 結(jié)尾的最大連續(xù)子序列是 4、–1棍鳖、2炮叶、1、–5渡处、4镜悉，所以 dp(8) = dp(7) + 4 = 5
狀態(tài)轉(zhuǎn)移方程：
- 如果 dp(i – 1) ≤ 0，那么 dp(i) = nums[i]
- 如果 dp(i – 1) > 0骂蓖，那么 dp(i) = dp(i – 1) + nums[i]
初始狀態(tài)
- dp(0) 的值是 nums[0]
最終的解
- 最大連續(xù)子序列和是所有 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 動(dòng)態(tài)規(guī)劃優(yōu)化
優(yōu)化空間，不需要數(shù)組
///
/// Author: liyanjun
/// description: 動(dòng)態(tài)規(guī)劃優(yōu)化
/// 優(yōu)化空間
///
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;
}
