HD-ACM算法专攻系列（22）——Max Sum

问题描述：

AC源码：

此题考察动态规划，解题思路：遍历（但有技巧），在于当前i各之和为负数时，直接选择以第i+1个为开头，在于当前i各之和为正数时，第i个可以不用作为开头（因为前i+1个之和一定大于第i+1个的值）

#include"iostream"

using namespace std;

int main()

{

    int t, n, start, end, sum, max, tmp;

    int a[100000];

    scanf("%d", &t);

    for(int i = 1; i <= t; i++)

    {

        if(i > 1)printf("\n");

        scanf("%d", &n);

        scanf("%d", a);

        max = a[0];

        start = end = 0;

        for(int j = 1; j < n; j++)

        {

            scanf("%d", a+j);

            if(a[j] > max)

            {

                max = a[j];

                start = end = j;

            }

        }

        for(int j = 0; j < n; j++)

        {

            if(a[j] >= 0)

            {

                sum = 0;

                tmp = j;

                for(int k = j; k < n; k++)

                {

                    sum += a[k];

                    if(sum > max)

                    {

                        max = sum;

                        start = tmp;

                        end = k;

                    }

                    if(sum >= 0)

                    {

                        j = k + 1;

                    }

                    else

                    {

                        break;

                    }

                }

            }

        }

        printf("Case %d:\n", i);

        printf("%d %d %d\n", max, start+1, end + 1);

    }

    return 0;

}