gpt4 book ai didi

algorithm - 动态规划算法(Kadane)

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:04:46 26 4
gpt4 key购买 nike

算法说明:最大子数组问题给定一个由 n 个实数组成的序列 A(1) … A(n),确定一个连续的子序列 A(i) … A(j),其中子序列中的元素之和最大。

算法:

int kadane(int a[], int n)
{
int overall_sum=0; //overall maximum subarray sum
int new_sum=0; //sum obtained by including the current element

for(int i=0;i<n;i++)
{
//new_sum is the maximum value out of current element or the sum of current element
//and the previous sum
new_sum=max(a[i], new_sum+a[i]);
cout << new_sum << " : ";
//if the calculated value of new_sum is greater than the overall sum,
//it replaces the overall sum value
overall_sum=max(overall_sum, new_sum);
cout << overall_sum << endl;
}

return overall_sum;

}

我知道我们正在尝试将问题分解为小的子问题。思路是确定n-1个子序列的最大部分和,求出n个序列的最大部分和。代码对我来说看起来很清楚,因为我可以在纸上解决它以找到解决方案,但这个想法似乎很神奇。有人可以对此算法提供更好的解释吗?或者它为什么有效的证明?

最佳答案

为了 100% 准确,算法实际计算的是:非空 子序列的最大总和,对于非空 数组(对于空数组为零,这有点不一致)。对于所有数字均为负数的数组,这会有所不同 - 如果我们将空序列计算为有效,则结果应为 0。对于这种情况,算法会生成最大的负数而不是 0。

证明:

在循环开始时,new_sum 始终是结束于(不包括)a[i] 的那些序列的最大总和(因此,直到 a[i-1] 代表 i>00 代表 i==0)。通过归纳循环执行来证明。这对于 i=0 显然是正确的(new_sum == 0 这是一个空序列的总和),并且对于 i+1 也是正确的> 赋值后,因为以a[i]结尾的最大和非空序列(即a[i+1]之前的最后一个元素)需要include a[i] 因此是 a[i] 本身的最大值以及 a[i] 和前面序列的总和。

overall_sum 只是 a[i] 的所有 new_sum 值中的最大值,因此代表最大的全局子序列(对于某些i 它必须以 a[i] 结束,因此对所有 a[i] 进行最大化工作。

关于algorithm - 动态规划算法(Kadane),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48004371/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com