快訊!我的新書登上天瓏網路書店11月份暢銷榜第一名啦!看過的都說讚!歡迎大家前往訂購!
>>>> AI 職場超神助手:ChatGPT 與生成式 AI 一鍵搞定工作難題 <<<<

最大子序列和問題

概念解釋

最大子序列和問題(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/


17年資歷女工程師,專精於動畫、影像辨識以及即時串流程式開發。經常組織活動,邀請優秀的女性分享她們的技術專長,並在眾多場合分享自己的技術知識,也活躍於非營利組織,辦理活動來支持特殊兒及其家庭。期待用技術改變世界。

如果你認同我或想支持我的努力,歡迎請我喝一杯咖啡!讓我更有動力分享知識!