概念解釋
最大子序列和問題（Maximum Slice Problem）是指在一個給定的整數序列中，找到一個連續子序列，使得子序列的和最大。
例如，在序列[-2, 1, -3, 4, -1, 2, 1, -5, 4]中，最大的子序列為[4, -1, 2, 1]，其和為6。
這個問題在實際應用中經常出現，比如在股票交易中，尋找一段時間內股票價格的最大漲幅，或者在信號處理中，尋找一段時間內信號的最大能量。
最大子序列和問題可以通過暴力枚舉和動態規劃兩種方法解決。暴力枚舉的時間複雜度為O(n^2)，動態規劃的時間複雜度為O(n)。其中，動態規劃是更加高效和常用的方法。
下面介紹一下動態規劃的解法思路：
設f[i]表示以第i個元素結尾的最大子序列和，那麼有：
f[i] = max(f[i-1] + nums[i], nums[i])
其中，nums是原始的整數序列，可以看出，f[i]的值只與f[i-1]和nums[i]有關。
狀態轉移方程表示以第i個元素結尾的最大子序列和要么是以第i-1個元素結尾的最大子序列和加上nums[i]得到，要么是只包含第i個元素。
最終的結果就是max(f[0], f[1], …, f[n-1])。
這個算法只需要遍歷一遍整個序列，時間複雜度為O(n)，是一個線性算法。因此，在解決最大子序列和問題時，動態規劃是一個高效的解法。
解題思路
假設我們有一個整數序列 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]，我們要找到一個連續子序列，使得子序列的和最大。
- 定義一個狀態數組 f，其中 f[i] 表示以第 i 個元素結尾的最大子序列和。初始時，f[0] = nums[0]。
- 現在開始遍歷整個序列，對於每個元素 nums[i]，我們需要計算以它為結尾的最大子序列和 f[i]。
對於 i = 1，我們有：f[1] = max(f[0] + nums[1], nums[1]) = max(-2 + 1, 1) = 1
對於 i = 2，我們有：f[2] = max(f[1] + nums[2], nums[2]) = max(1 – 3, -3) = -2 - 以此類推，我們繼續遍歷整個序列，計算出所有的 f[i]。最後，最大的子序列和即為 max(f[0], f[1], …, f[n-1])。
function maxSubarray(nums) {
if (!nums || nums.length === 0) {
return 0;
}
let maxSum = nums[0];
let curSum = nums[0];
for (let i = 1; i < nums.length; i++) {
curSum = Math.max(nums[i], curSum + nums[i]);//要不要包含前面的
maxSum = Math.max(maxSum, curSum);//要不要包含自己
}
return maxSum;
}
解題練習 – MaxProfit
題目連結: MaxProfit
function solution(A) {
if(A.length <= 1){
return 0
}
var diff = []
var current_diff = 0
for (var i = 1; i < A.length; i++) {
current_diff = A[i] - A[i - 1]
diff.push(current_diff)
}
var max_sum = diff[0]
var curr_sum = diff[0]
for (var i = 1; i < diff.length; i++) {
curr_sum = Math.max(diff[i], curr_sum + diff[i]);
max_sum = Math.max(curr_sum, max_sum);
}
return max_sum < 0 ? 0:max_sum
}
https://app.codility.com/demo/results/training4F3SK7-QSS/
解題練習 – MaxSliceSum
題目連結: MaxSliceSum
function solution(A) {
if(A.length == 0) return 0
var cur_sum = A[0]
var max_sum = A[0]
for(var i=1;i<A.length;i++){
cur_sum = Math.max(A[i], cur_sum+A[i])
max_sum = Math.max(max_sum, cur_sum)
}
return max_sum
}
https://app.codility.com/demo/results/trainingX4VPNP-3QU/
