杭电1003（大数）简单的DP简单过

此题名字是大数，其实不用long int 也是可以Ac的，不过用了还是好些，毕竟大赛中测试数据还是比较好的，这是个典型的DP类的最大子序列题。这道题影藏了很多细节，好多人的代码和杭电的大神贴出来的参考代码都是一样的，但是就是不给Ac，这种情况很多，关键是很多时候要考虑边界情况，因为杭电的测试中很多组数据必定会包含有他的各个方向，大部分都是用于看率步骤而导致的。下面选择几种方法浅谈一下：

? ? 如果只是求最长子序列我想还是很简单的，关键是还要输出他的起始端的数字，这个就有点麻烦了。

? ?题目的大意是给你一段数字，要求是求出连续的一段中可能的数字的和的最大值。对于每个测试的情况下，你应该输出两行，第一行是“案例：”＃意味着测试用例数，第二行包含三个整数序列中，最大琛子的起始位置序列的子序列的结束位置，如果有一个以上的结果，输出的第一个输出一个空行之间的两种情况。

? ? ?方法一（整个考虑）：

? ?因为题目中是每个数字都-1000到1000.所以我们可以用一个数（小于-1000即可）这是因为这个数是用来记录一连串数字的和的，由于不知道第一个输入的输的大小，所以应该以最小的数来考虑。

? ? 下面以代码来分析一下：

#include<iostream>
#include<vector>
using namespace std;
int main()
{
? ? int T,n,i,start,end,k;
? ? cin>>T;
? ? for(int j=1;j<=T;j++)因为下面需要输出数字串的起始与结束位置，其与i有关故在此将i设计为从1开始
? ? {
? ? ? ? cin>>n;
? ? ? ? vector<int>arr(n+1,0); ?这个是表示建立一个容器，里面有n+1个变量，每个变量初始化为0他的作用类似于数组
? ? ? ? int sum=0;
? ? ? ? start=end=k=1;
? ? ? ? int maxn=-1001 ;
? ? ? ? for(i=1;i<=n;i++)
? ? ? ? {
? ? ? ? ? ? cin>>arr[i];
? ? ? ? ? ? sum+=arr[i];
? ? ? ? ? ? ?if(maxn<sum)这一句就是为了找出在数字串的最大值。sum是记录数字串相加的大小，如果有大的就交换值
? ? ? ? ? ? ?{?

? ? ? ? ? ? maxn=sum;
? ? ? ? ? ? ? ?end=i; ? ? ? ? ? ?只要是数字串的只在增大就表示着个数字是可以加上去的；所以结束的得地方是和i是同步的
? ? ? ? ? ? ?
? ? ? ? ? ? ? start=k;//设计的时候始终记住就是这两个数是同是在成功的时候可以变得，

? ? ? ? ? ? ? ?但是开始的数字就是在不成功的时候也是会变化的，

? ? ? ? ? ? ? ? ?所以我们要记住在这种情况下，就是要定格
? ? ? ? ? ? ?}
? ? ? ? ?if(sum<0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? sum=0 ; ? ? ? ?当sum的结果是负数时，我们就把下一个数组的值交给sum，比如2，-3，这时sum=-1，我们就不要这个结果了，

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?因为他已经不可能是最大值了，就令sum=0；相加是在上面事实现的。

? ? ? ? ? ? ? ? k=i+1; ? ? ? ? ? 这个时候初始的地方也是要变得如上面的2，-3，原来是start=1，这时直接转到3上因为i=2了。
? ? ? ? ? ? }
? ? ? ? ? ?
? ? ? ? }
? ? ? ? cout<<"Case "<<j<<":n"<<maxn<<" "<<start<<" "<<end<<endl;
? ? ? ? if(j!=T)cout<<endl;
? ? }
? return 0;
}

下面贴几个例子，如果这几个例子过了就差不多了

-1 ?-2 ?-3 10（在此省略了前面的数字，下同）

结果：Case 1: 10 4 4

1 2 3 -100 1 2 3 -100 1 2 2 2 2

结果Case 2：9 9 13

-1 -2 -3 -4 -5

结果：Case ?3:-1 1 1

-3 -2 -1 -2 -3?

结果：Case 4：-1 3 3?

?0 0 2 0

结果：Case ：2 1 3

如果上诉结果都没有对的话是不可能Ac的，那就是自己的程序的问题了。