引言
在做KB的基礎DP練習題的時候遇到了最大子序列和的變種問題，突然發現自己以前沒做過解題筆記（現補上）
最大子序列和是一道經典的算法題， leetcode 也有原題《53.maximum-sum-subarray》，今天我們就來徹底攻克它。
題目描述
求取數組中最大連續子序列和，例如給定數組為 A = [1， 3， -2， 4， -5]， 則最大連續子序列和為 6，即 1 + 3 +（-2）+ 4 = 6。
去
首先我們來明確一下題意。
- 題目說的子數組是連續的
- 題目只需要求和，不需要返回子數組的具體位置。
- 數組中的元素是整數，但是可能是正數，負數和 0。
- 子序列的最小長度為 1。
比如：
- 對於數組 [1, -2, 3, 5, -3, 2], 應該返回 3 + 5 = 8
- 對於數組 [0, -2, 3, 5, -1, 2], 應該返回 3 + 5 + -1 + 2 = 9
- 對於數組 [-9, -2, -3, -5, -3], 應該返回 -2
解法一 – 暴力法（超時法）
一般情況下，先從暴力解分析，然後再進行一步步的優化。
思路
我們來試下最直接的方法，就是計算所有的子序列的和，然後取出最大值。
記 Sum[i,….,j]為數組 A 中第 i 個元素到第 j 個元素的和，其中 0 <= i <= j < n，
遍歷所有可能的 Sum[i,….,j] 即可。
我們去枚舉以 0,1,2…n-1 開頭的所有子序列即可，
對於每一個開頭的子序列，我們都去枚舉從當前開始到 n-1 的所有情況。
這種做法的時間複雜度為 O(N^2), 空間複雜度為 O(1)。
代碼
Java：
class MaximumSubarrayPrefixSum {
public int maxSubArray(int[] nums) {
int len = nums.length;
int maxSum = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < len; i++) {
sum = 0;
for (int j = i; j < len; j++) {
sum += nums[j];
maxSum = Math.max(maxSum, sum);
}
}
return maxSum;
}
}
Python 3:
import sys
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
maxSum = -sys.maxsize
sum = 0
for i in range(n):
sum = 0
for j in range(i, n):
sum += nums[j]
maxSum = max(maxSum, sum)
return maxSum
空間複雜度非常理想，但是時間複雜度有點高。怎麼優化呢？我們來看下下一個解法。
解法二 – 分治法
思路
我們來分析一下這個問題， 我們先把數組平均分成左右兩部分。
此時有三種情況：
- 最大子序列全部在數組左部分
- 最大子序列全部在數組右部分
- 最大子序列橫跨左右數組
對於前兩種情況，我們相當於將原問題轉化為了規模更小的同樣問題。
對於第三種情況，由於已知循環的起點（即中點），我們只需要進行一次循環，分別找出
左邊和右邊的最大子序列即可。
所以一個思路就是我們每次都對數組分成左右兩部分，然後分別計算上面三種情況的最大子序列和，
取出最大的即可。
舉例說明，如下圖：
這種做法的時間複雜度為 O(N*logN), 空間複雜度為 O(1)。
代碼
Java:
class MaximumSubarrayDivideConquer {
public int maxSubArrayDividConquer(int[] nums) {
if (nums == null || nums.length == 0) return 0;
return helper(nums, 0, nums.length - 1);
}
private int helper(int[] nums, int l, int r) {
if (l > r) return Integer.MIN_VALUE;
int mid = (l + r) >>> 1;
int left = helper(nums, l, mid - 1);
int right = helper(nums, mid + 1, r);
int leftMaxSum = 0;
int sum = 0;
// left surfix maxSum start from index mid - 1 to l
for (int i = mid - 1; i >= l; i--) {
sum += nums[i];
leftMaxSum = Math.max(leftMaxSum, sum);
}
int rightMaxSum = 0;
sum = 0;
// right prefix maxSum start from index mid + 1 to r
for (int i = mid + 1; i <= r; i++) {
sum += nums[i];
rightMaxSum = Math.max(sum, rightMaxSum);
}
// max(left, right, crossSum)
return Math.max(leftMaxSum + rightMaxSum + nums[mid], Math.max(left, right));
}
}
Python 3 :
import sys
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
return self.helper(nums, 0, len(nums) - 1)
def helper(self, nums, l, r):
if l > r:
return -sys.maxsize
mid = (l + r) // 2
left = self.helper(nums, l, mid - 1)
right = self.helper(nums, mid + 1, r)
left_suffix_max_sum = right_prefix_max_sum = 0
sum = 0
for i in reversed(range(l, mid)):
sum += nums[i]
left_suffix_max_sum = max(left_suffix_max_sum, sum)
sum = 0
for i in range(mid + 1, r + 1):
sum += nums[i]
right_prefix_max_sum = max(right_prefix_max_sum, sum)
cross_max_sum = left_suffix_max_sum + right_prefix_max_sum + nums[mid]
return max(cross_max_sum, left, right)
解法三 – 動態規劃
思路
我們來思考一下這個問題， 看能不能將其拆解為規模更小的同樣問題，並且能找出
遞推關係。
我們不妨假設問題 Q(list, i) 表示 list 中以索引 i 結尾的情況下最大子序列和，
那麼原問題就轉化為 Q(list, i), 其中 i = 0,1,2…n-1 中的最大值。
我們繼續來看下遞歸關係，即 Q(list, i)和 Q(list, i – 1)的關係，
即如何根據 Q(list, i – 1) 推導出 Q(list, i)。
如果已知 Q(list, i – 1)， 我們可以將問題分為兩種情況，即以索引為 i 的元素終止，
或者只有一個索引為 i 的元素。
- 如果以索引為 i 的元素終止， 那麼就是 Q(list, i – 1) + list[i]
- 如果只有一個索引為 i 的元素，那麼就是 list[i]
分析到這裏，遞推關係就很明朗了，即Q(list, i) = Math.max(0, Q(list, i - 1)) + list[i]
舉例說明，如下圖：
這種算法的時間複雜度 O(N), 空間複雜度為 O(1)
代碼
Java:
class MaximumSubarrayDP {
public int maxSubArray(int[] nums) {
int currMaxSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < nums.length; i++) {
currMaxSum = Math.max(currMaxSum + nums[i], nums[i]);
maxSum = Math.max(maxSum, currMaxSum);
}
return maxSum;
}
}
Python 3:
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
max_sum_ending_curr_index = max_sum = nums[0]
for i in range(1, n):
max_sum_ending_curr_index = max(max_sum_ending_curr_index + nums[i], nums[i])
max_sum = max(max_sum_ending_curr_index, max_sum)
return max_sum
解法四 – 數學分析
思路
我們來通過數學分析來看一下這個題目。
我們定義函數 S(i) ，它的功能是計算以 0（包括 0）開始加到 i（包括 i）的值。
那麼 S(j) – S(i – 1) 就等於 從 i 開始（包括 i）加到 j（包括 j）的值。
我們進一步分析，實際上我們只需要遍歷一次計算出所有的 S(i), 其中 i 等於 0,1,2….,n-1。
然後我們再減去之前的 S(k),其中 k 等於 0，1，i – 1，中的最小值即可。 因此我們需要
用一個變量來維護這個最小值，還需要一個變量維護最大值。
這種算法的時間複雜度 O(N), 空間複雜度為 O(1)。
其實很多題目，都有這樣的思想， 比如之前的《每日一題 – 電梯問題》。
代碼
Java:
class MaxSumSubarray {
public int maxSubArray3(int[] nums) {
int maxSum = nums[0];
int sum = 0;
int minSum = 0;
for (int num : nums) {
// prefix Sum
sum += num;
// update maxSum
maxSum = Math.max(maxSum, sum - minSum);
// update minSum
minSum = Math.min(minSum, sum);
}
return maxSum;
}
}
Python 3:
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
maxSum = nums[0]
minSum = sum = 0
for i in range(n):
sum += nums[i]
maxSum = max(maxSum, sum - minSum)
minSum = min(minSum, sum)
return maxSum
總結
我們使用四種方法解決了《最大子序列和問題》,
並詳細分析了各個解法的思路以及複雜度，相信下次你碰到相同或者類似的問題
的時候也能夠發散思維，做到一題多解，多題一解。
實際上，我們只是求出了最大的和，如果題目進一步要求出最大子序列和的子序列呢？
如果要題目允許不連續呢？ 我們又該如何思考和變通？如何將數組改成二維，求解最大矩陣和怎麼計算？
這些問題留給讀者自己來思考。
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※別再煩惱如何寫文案,掌握八大原則!
※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!
※超省錢租車方案
※教你寫出一流的銷售文案?
※網頁設計最專業,超強功能平台可客製化
