专栏首页CSDN旧文动态规划经典算法--最大子段和

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

状态转移方程:

f[i]=max(a[i],f[i-1]+a[i])    //要么舍弃,要么累加
即:前端序列小于0舍去,前子段大于0,不要白不要,加上!
#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 条评论
登录 后参与评论

相关文章

  • 树上倍增法求LCA

    1.两结点的深度相同. 2.两结点深度不同. 第一步都要转化为情况1,这种可处理的情况。

    风骨散人Chiam
  • 图论-网络流-最大流--POJ1273Drainage Ditches(Dinic)

    Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite...

    风骨散人Chiam
  • 图论--LCA--树上倍增法(在线)

    风骨散人Chiam
  • (31) 剖析Arrays / 计算机程序的思维逻辑

    数组是存储多个同类型元素的基本数据结构,数组中的元素在内存连续存放,可以通过数组下标直接定位任意元素,相比我们在后续章节介绍的其他容器,效率非常高。 数组操作是...

    swiftma
  • LeetCode 137 Single Number II

    ShenduCC
  • P2279 [HNOI2003]消防局的设立

    题目描述 2020年,人类在火星上建立了一个庞大的基地群,总共有n个基地。起初为了节约材料,人类只修建了n-1条道路来连接这些基地,并且每两个基地都能够通过道路...

    attack
  • 水题 提取不重复的整数 (queue的练习)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • SPOJ 375 边操作

    给一颗树,每条边有一个权值。有两种操作:1、修改某条边的值;2、询问a、b两点路径上边权的最大值。

    用户2965768
  • 懂二进制

    题目描述 世界上有10种人,一种懂二进制,一种不懂。那么你知道两个int32整数m和n的二进制表达,有多少个位(bit)不同么? 输入例子: 19...

    AI那点小事
  • BZOJ 4289: PA2012 Tax(最短路)

    Description 给出一个N个点M条边的无向图,经过一个点的代价是进入和离开这个点的两条边的边权的较大值,求从起点1到点N的最小代价。起点的代价是离开起...

    attack

扫码关注云+社区

领取腾讯云代金券