searchusermenu
  • 发布文章
  • 消息中心
点赞
收藏
评论
分享
原创

最大子段和-算法学习

2023-07-12 04:00:51
0
0

题目详情:
给出一个长度为 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));

0条评论
作者已关闭评论
t****m
98文章数
1粉丝数
t****m
98 文章 | 1 粉丝
t****m
98文章数
1粉丝数
t****m
98 文章 | 1 粉丝
原创

最大子段和-算法学习

2023-07-12 04:00:51
0
0

题目详情:
给出一个长度为 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));

文章来自个人专栏
js
57 文章 | 1 订阅
0条评论
作者已关闭评论
作者已关闭评论
0
0