子串和

子串和

描述

给定一整型数列{a1,a2...,an},找出连续非空子串{ax,ax+1,...,ay},使得该子序列的和最大,其中,1<=x<=y<=n。

输入第一行是一个整数N(N<=10)表示测试数据的组数) 每组测试数据的第一行是一个整数n表示序列中共有n个整数,随后的一行里有n个整数I(-100=<I<=100),表示数列中的所有元素。(0<n<=1000000)输出对于每组测试数据输出和最大的连续子串的和。样例输入

1
5
1 2 -1 3 -2

样例输出

5
 
#include <iostream>
#include <string>
#include <stack>
#include <set>
#include <memory.h>
#include <map>
#include <iomanip>
#include <queue>
#include <algorithm>

#define max(a,b) (a>b ? a:b)
using namespace std;

int dp[1000001];
int arr[1000001];
int main()
{
    int n;
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        int flag = 0;
        int M = -99999999;
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
            if (arr[i]>0)
                flag = 1;
            if (arr[i] > M)
                M = arr[i];
        }
        if (flag == 0)
        {
            cout << M << endl;
            continue;
        }

        memset(dp, 0, sizeof(dp));
        dp[0] = arr[0];
        int Max = -9999999;
        for (int i = 1; i < n; i++)
        {
            if (dp[i - 1] >= 0)
                dp[i] = dp[i - 1] + arr[i];
            else
                dp[i] = arr[i];

            if (dp[i]>Max)
                Max = dp[i];
        }

        cout << Max<< endl;
    }
    return 0;
}        

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 拦截导弹

    某国为了防御敌国的导弹袭击,发展中一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于等于前一发...

    书童小二
  • 苹果

    ctest有n个苹果,要将它放入容量为v的背包。给出第i个苹果的大小和价钱,求出能放入背包的苹果的总价钱最大值。

    书童小二
  • 三个数从小到大排序

    书童小二
  • POJ 2192 Zipper HDU 2059 龟兔赛跑

    owent
  • 浅析强连通分量 Tarjan

    在有向图G中,如果两点互相可达,则称这两个点强连通,如果G中任意两点互相可达,则称G是强连通图。

    用户2965768
  • FZU 2098 刻苦的小芳(卡特兰数,动态规划)

    Problem 2098 刻苦的小芳 Accept: 42 Submit: 70 Time Limit: 1000 mSec Memory ...

    ShenduCC
  • 均摊复杂度和防止复杂度的震荡

    关于上一节中我们对添加操作的时间复杂度归结为O(n)是考虑了扩容操作(resize)在内的。就addLast(e)操作而言,时间复杂度为O(1),在考虑最坏情况...

    wfaceboss
  • 在 Linux 中永久并安全删除文件和目录 只需这 3 招

    在大多数情况下,我们习惯于使用 Delete 键、垃圾箱或 rm 命令从我们的计算机中删除文件,但这不是永久安全地从硬盘中(或任何存储介质)删除文件的方法。

    哲洛不闹
  • 关于Redis RedLock算法的争论

    内容简介:Martin上来就问,我们要锁来干啥呢?2个原因:对于第1种原因,我们对锁是有一定宽容度的,就算发生了两个节点同时工作,对系统的影响也仅仅是多付出了一...

    stys35
  • Linux进程通信——共享存储

    共享内存是进程间通信最有用的方式,也是最快的IPC形式。共享内存是说:同一块内存被映射到多个进程的地址空间。但是共享内存并不提供同步机制,因此需要互斥锁或者信号...

    zy010101

扫码关注云+社区

领取腾讯云代金券