动态规划经典算法--最大子段和

状态转移方程：

代码语言：javascript复制

f[i]=max(a[i],f[i-1] a[i])    //要么舍弃，要么累加
即：前端序列小于0舍去，前子段大于0，不要白不要，加上！

代码语言：javascript复制

#include <bits/stdc  .h>
using namespace std;
//---------------https://lunatic.blog.csdn.net/-------------------//
int data[100000];
int maxsum(int *a, int ln)
{
    int maxi = 0, ans = 0;
    for (int i = 1; i <= ln; i  )
    {
        if (maxi < 0)
            maxi = data[i];
        else maxi =data[i];
        ans = max(ans, maxi);
    }
    return ans;
}
int main()
{
    int len;
    cin >> len;
    for (int i = 1; i <= len; i  )
        cin >> data[i];
    cout << maxsum(data, len);
}

动态规划

0 人点赞