图片说明
今天，我们来讲一讲动态规划初级篇（入门题目）。
题目如上：其题目意思是输入一行N，接下来输入N行（即测试的用例数），对于每一个测试用例输入一行，输入第一个数字我们用n表示，其后面跟的n个数字我们用数组a[]表示（我们数组从下标1开始），而对于数组，找出连续的几个数字之和最大的，并且输出最大值和该区间的左右端点下标，就如下面这个用例：5 6 -1 5 4 -7，该行有六个数字，第一个数字为5，所以后面跟5个数字，6 -1 5 4 -7。然后在这后面五个数字中，找出一个连续的区间，该区间所有值之和最大。我们可以看出，区间1-4的所有值加起来最大，值为6+（-1）+5+4=14，所以输出第一行Case 1：，第二行14 1 4。
接下来，我们主要介绍一下该动态规划的基本思路：
在此之前，我们先介绍一下这几个变量的作用。
const int mod=1e4;
a[mod]:用来表示每组数据跟在第一个数后面的数字，但在遍历的过程中，a[i]表示的是将从beg到当前位置之间所有元素的和。
left:用来记录我们答案要求的满足条件的区间左端。
right：用来标记最后满足条件的区间的右端。
maxn：用来记录遍历过程的最大值。
beg：用来更新区间左端点。（注意，这里要与left的作用区分开来，left是记录最终答案的左区间，而beg是用来寻找答案区间的左端点的位置。例如-7 3 5 -9 10，用于第一个数为负数，那么肯定不能将left置为1，即答案的区间不能从1开始，所以beg就是用来更新left的）。

lef=1;
righ=1;
beg=1;
maxn=a[1];
for(int i=2;i<=n;i++){
    if(a[i-1]>=0) a[i]=a[i]+a[i-1];  //该上一个元素大于等于0 
    else  beg=i;  //否则就将开始先设为当前位置 
    if(a[i]>maxn){  //如果遇到大于maxn的 
        maxn=a[i];
            lef=beg;
            righ=i;
    }
}

其实整个程序的核心就是这段代码。对数组进行遍历，先将left，right置为1，另maxn为a[1],从2开始遍历数组，如果在遍历a[i]元素之前，该区间的和已经小于0了，那么就将beg置为当前的i。否则，继续将a[i]=a[i]+a[i-1]。但是，如果遇到此时的a[i]，在进行完上述步骤之后发现大于maxn，则对maxn进行更新，同时，将left也更新为当前情况下的beg，将right也置为i。直至循环结束。

#include<iostream>
using namespace std;
const int mod=1e5+7;
int a[mod];
int n,maxn;
int lef,righ,beg;
int main(){
    int t;
    cin>>t;
    for(int j=0;j<t;j++){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        maxn=0;
        lef=1;
        righ=1;
        beg=1;
        maxn=a[1];
        for(int i=2;i<=n;i++){
            if(a[i-1]>=0) a[i]=a[i]+a[i-1];  //该上一个元素大于等于0 
            else  beg=i;  //否则就将开始先设为当前位置 
            if(a[i]>maxn){  //如果遇到大于maxn的 
                maxn=a[i];
                lef=beg;
                righ=i;
            }
        }
        //这些都是按题目格式输出，这不是重点，重点是上面的这个循环
        cout<<"Case "<<j+1<<":"<<endl;
        cout<<maxn<<" "<<lef<<" "<<righ<<endl;
        if(j<t-1)  cout<<endl;
    }
    return 0;
}

如果还不理解的，请先看看我之前写的牛客博客寒假集训营2的题解C题：https://blog.nowcoder.net/n/9d821b9b4f2445749680a2777d4746cd
有疑问下方留言。