Max Sum HDU - 1003

周二 (10.16) TEST<19>

A - Max Sum HDU - 1003

解题思路 动态规划

由于 要求 求出最大子区间和 并且 输出区间 起点/终点;
分析: 所以存在 几种情况

1. 都是负数/0
   
2. 多段 正数 负数相间分布 类似于 +-+---+++-
   2.1 前一段正数和 后一段负数 相加 得数为 正
   2.2 前一段正数和 后一段负数 相加 得数为 负
   对于第一种情况 比较最大值就行
   对于2.1 要考虑 后面对前面的影响 可能会出现 越加越大 或者(越加 也没有之前的 呢个大)
   所以 也需要 比较最大值
   对于2.2 来说 没有必要进行比较 因为...你都有正数了 最后和得出的还是负数 肯定正的大

对于 区间的记录需要有 更新操作 具体看代码分析

AC代码如下:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[100005];//记录数组
int main(){
   int t;//组数
   cin>>t;
   for(int i=1;i<=t;i++){
    int n;
       cin>>n;//各组个数
       memset(dp,0,sizeof(dp));
    for(int j=1;j<=n;j++)
    cin>>dp[j];
    int l=1,r=1;//初始化 必须为1 因为m-1 导致必须
    /*将起始 终点 为1  就是 第一个点就是最大的*/
    int temp=1;//temp也必须 1  因为本身 就可能正区间是从1 开始 的
    int maxx=dp[1];//同temp
    for(int m=2;m<=n;m++){
        if(dp[m-1]>=0)   //这里必须要 >=0题目要求 第一次出现 最大值的位置 有可能会出现一种情况
        /*   +--+  这种情况 到第三位时刚好为0  这样就使得 1-4之和等于 4位置
         而样例也 是 输出的   1 6  而不是6 6  */
        dp[m]=dp[m]+dp[m-1];//正数 不确定性   可能存在2.1  的两种情况
        else
        temp=m;//这样更新 区间起始点 保证+---+ 一定是正或者为-0--0-
        if(dp[m]>maxx){//更大值出现更新
            maxx=dp[m];
            l=temp;
            r=m;
        }
    }
    if(i>1)
    cout<<endl;
    printf("Case %d:\n%d %d %d\n",i,maxx,l,r);
   }
    return 0;
}