欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最大子段和-动态规划

程序员文章站 2022-07-12 08:41:09
...

最大子段和-动态规划写法

题目:

给定长度为n的整数序列,a[1…n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大.或者求出最大的这个和.例如(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为[2,4]。
有俩种dp做法:

法一:

用数组dp,这里可以假设dp[i]是最大字段和的最后一个,那么他肯定是前面的dp[i-1]和此位置的a[i]结合,或者是a[i]。
例如(-2,11,-4,13,-5,2),这里我是下标从1开始,dp[0]的初值为无穷小,所以dp[1]就可以和dp[0]+a[1]和a[1]进行比较。所以此时dp[1]=-2,然后dp[2]的值就是11,以此类推dp[3]的值是7,dp[4]的值是20,dp[5]的值是15,dp[6]的值是17,得出dp方程为dp[i]=max(dp[i],d[i-1]+a[i])。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <map>
#include <math.h>
#include <set>
#include <vector>
#define ll long long
using namespace std;
const int AXF=0x3f3f3f3f;
const int maxn=100010;
ll dp[maxn],a[maxn];
int main()
{
 int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        dp[i] = a[i];
    }
    dp[0]=-AXF;
    for(int i = 1; i <= n; i++)
        dp[i] = max(dp[i], dp[i - 1] + a[i]);
    ll ans = 0;
    for(int i = 1; i <= n; i++)ans = max(ans, dp[i]);
    cout<<ans<<endl;
    return 0;
}

法二:
根据法一优化得来的方法,你是不是发现可以拿个变量记住d[i-1],然后可以一边比较一边更新ans!

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <map>
#include <math.h>
#include <set>
#include <vector>
#define ll long long
using namespace std;
const int AXF=0x3f3f3f3f;
int main()
{
 int n;
    cin >> n;
    int ans=-AXF,m=-AXF;//定义初始值 
    for(int i = 1; i <= n; i++)
    {
     int a;
        cin >> a;
        m=max(a,m+a);
        if(m>ans)ans=m;
    }
    cout<<ans<<endl;
    return 0;
}
相关标签: 题解