Posted on by

最大子序列和問題

概念解釋

最大子序列和問題（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]，我們要找到一個連續子序列，使得子序列的和最大。

  1. 定義一個狀態數組 f，其中 f[i] 表示以第 i 個元素結尾的最大子序列和。初始時，f[0] = nums[0]。
  2. 現在開始遍歷整個序列，對於每個元素 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
  3. 以此類推，我們繼續遍歷整個序列，計算出所有的 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/