题目详情:
给出一个长度为 n 的序列 a,选出其中连续且非空的一段使得这段和最大。
示例:
输入:
第一行是一个整数,表示序列的长度 n。
第二行有 n个整数,第 i 个整数表示序列的第 i 个数字 ai
输出:
输出一行一个整数表示答案。
解题思路:
可以使用动态规划来解决这个问题。我们定义一个数组dp,其中dp[i]表示以第i个元素结尾的连续子数组的最大和。
首先,定义一个变量maxSum,用来记录全局最大和的值,初始值设为序列的第一个数字a[0]。
然后,遍历序列的每个元素a[i],从第二个元素开始。
对于第i个元素,我们有两种选择:
将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])。
同时,更新maxSum的值,如果dp[i]大于maxSum,则将其赋值给maxSum。
最后,遍历完整个序列后,maxSum的值即为所求的连续子数组的最大和。
代码实现:
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));