题目地址：

一、题目要求

给出几组整型数据，每组数据在最开始都会给出数据的数量，根据给出的数据，求这组数据中最大的连续子串的和是多少，并写出此时子串的左、右边界（输出的左右边界从1起算）

二、程序代码

代码思路详见注释

#include
    
     using namespace std;int main(){    int counter;     //计数器    int countera;    //计数器a，用于统计一共有多少组数据    int counterb;    //计数器b，用于统计每组数据中的数据数    int i, j;        //for语句遍历用变量    int sum;         //临时计算的各数字和    int maxsum;      //数字串中的最大子串和    int left, right; //取最大子串和时的左边界和右边界    cin >> countera;    for(counter = 1; counter <= countera; counter++)    {        maxsum = -1001;        //依次读入数据时，maxsum被设置为数组中的最大值        cin >> counterb;        int* array = new int[counterb];        for(i = 0; i < counterb; i++)        {            cin >> array[i];            if(array[i] > maxsum)            {                maxsum = array[i];                left = i;                right = i;            }        }        for(i = 0; i < counterb; i++)        {            //除了自己单独成串的情况（前面已经考虑过）            //负数不能作为max子串的第0项            if(array[i] < 0)            {                continue;            }            //考察从数组array第i项开始的各子串            sum = 0;            for(j = i; j < counterb; j++)            {                sum += array[j];                //子串数字和大于maxsum的情况下                //将maxsum与左右边界设定为当前状态                if(sum > maxsum)                {                    maxsum = sum;                    left = i;                    right = j;                }                //如果sum小于0，则后面的子串不必考察                //因为后面的串再大，加上前面小于0的sum也是累赘                //不可能再得出新的最大子串                if(sum < 0)                {                    break;                }            }        }        //输出计算结果        cout << "Case " << counter << ':' << endl;        cout << maxsum << ' ' << left + 1 << ' ' << right + 1 << endl;        if(counter != countera)        {            cout << endl;        }    }    return 0;}
    

三、之前写的超时代码（穷举法）

#include
    
     using namespace std;int main(){    int counter, countera, counterb;    int i, j, k, sum, maxsum, left, right;    //读取数据组数    cin >> countera;    for(counter = 1; counter <= countera; counter++)    {        //依次读入各组数据        cin >> counterb;        int* array = new int[counterb];        for(i = 0; i < counterb; i++)        {            cin >> array[i];        }        maxsum = array[0];        //逐个子串比对        for(i = 0; i < counterb; i++)        {            for(j = i; j < counterb; j++)            {                //计算子串数字和                sum = 0;                for(k = i; k <= j; k++)                {                    sum += array[k];                }                //数字和大于maxsum则更新maxsum                if(sum > maxsum)                {                    left = i;                    right = j;                    maxsum = sum;                }            }        }        cout << "Case " << counter << ':' << endl;        cout << maxsum << ' ' << left + 1 << ' ' << right + 1 << endl;        if(counter != countera)        {            cout << endl;        }    }    return 0;}
    

END