題目詳情:
給出一個長度為 n 的序列 a,選出其中連續且非空的一段使得這段和最大。
示例:
輸入:
第一行是一個整數,表示序列的長度 n。
第二行有 n個整數,第 i 個整數表示序列的第 i 個數字 ai
輸出:
輸出一(yi)行一(yi)個整數表示答案。
解題思路:
可以(yi)使(shi)用動態規劃來解決這個(ge)問題。我們定(ding)義一(yi)個(ge)數組(zu)(zu)dp,其(qi)中dp[i]表示以(yi)第i個(ge)元(yuan)素結尾的(de)連續子數組(zu)(zu)的(de)最大(da)和。
首先,定義一個變量maxSum,用來記錄全局最大和的值,初始值設為序列的第一個數字a[0]。
然后,遍歷序列的每個元素a[i],從第二個元素開始。
對于(yu)第i個元(yuan)素,我們有兩種選擇:
將a[i]加入到前面的連續子數組中,得到新的連續子數組和:dp[i] = dp[i-1] + a[i]。
開始一個新的連續子數組,只包含當前元素:dp[i] = a[i]。
然后選取這兩個選擇中較大的那個作為dp[i]的值,即dp[i] = max(dp[i-1] + a[i], a[i])。
同(tong)時,更(geng)新maxSum的值(zhi),如果dp[i]大于maxSum,則(ze)將其賦值(zhi)給(gei)maxSum。
最后,遍歷完整(zheng)個(ge)序列后,maxSum的值即(ji)為(wei)所求的連續子數組的最大和。
代碼實現:
function findMaxSubarraySum(n, arr) {
let maxSum = arr[0];
let dp = [arr[0]];
for (let i = 1; i < n; i++) {
dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
maxSum = Math.max(maxSum, dp[i]);
}
return maxSum;
}
// 示例輸入
const n = 7;
const arr = [2, -4, 3, -1, 2, -4, 3];
// 調用函數并輸出結果
console.log(findMaxSubarraySum(n, arr));