动态规划

记录点滴。

/*
2015.6    HT
ACM Work_5

*/

#include <iostream>
#include <algorithm>
using namespace std;

/*
数塔
要求从顶层走到底层，若每一步只能走到相邻的结点
采用自底向上方法，当前层的数的值由下一层的两个数的值决定
Input:
1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Output:
30
*/
//int main()
//{
//    int t, n, x[102][102];
//    cin >> t;
//    while (t--)
//    {
//        cin >> n;
//        for (int i = 0; i<n; i++)
//        for (int j = 0; j <= i; j++)
//            cin >> x[i][j];
//        for (int i = n - 2; i >= 0; i--)
//        for (int j = 0; j <= i; j++)
//            x[i][j] = x[i][j] + max(x[i + 1][j], x[i + 1][j + 1]);
//
//        cout << x[0][0] << endl;
//    }
//    return 0;
//}



/*
免费馅饼
0-1-2-3-4-5-6-7-8-9-10
*/
//int c[1000][11];
//
//int max1(int a, int b, int c)
//{
//    a = a>b ? a : b;
//    a = a>c ? a : c;
//    return a;
//}
//
//int main()
//{
//    int n, a, b;
//    while (cin >> n && n)
//    {
//        int m = 0;
//        memset(c, 0, sizeof(c));
//        while (n--)
//        {
//            // 坐标点        落下时刻
//            scanf_s("%d%d", &a, &b);
//            c[b][a]++;
//            if (m < b)
//                m = b;
//        }
//        for (int i = m - 1; i >= 0; i--)
//        {
//            for (int j = 1; j <= 9; j++)
//                c[i][j] = c[i][j] + max1(c[i + 1][j - 1], c[i + 1][j], c[i + 1][j + 1]);
//            c[i][0] = c[i][0] + max(c[i + 1][0], c[i + 1][1]);
//            c[i][10] = c[i][10] + max(c[i + 1][9], c[i + 1][10]);
//        }
//        cout << c[0][5] << endl;
//    }
//    return 0;
//}



/*
Super Jumping! Jumping! Jumping!
求解最大递增子序列和

如：3 1 4
如果第二个数大于第一个数，dp[2]=dp[1]+num[2]；如果不大，dp[2]=num[2]; dp[3]=7表示三个数的最大值
首先比较num[3]和num[1],如果num[3]>num[1],dp[3]=7先存下来,如果num[3]>num[2],dp[3]=5依旧存下来;
还有一种如果num[3]比前两个值都小，dp[3]=num[3]; 最后在存下来的dp[3]中找到一个最大的
*/
//int num[1010], dp[1010];
//
//int main()
//{
//    int n, Max;
//    while (cin >> n)
//    {
//        if (n == 0)
//            break;
//        Max = 0;
//        memset(dp, 0, sizeof(dp));
//        for (int i = 0; i < n; i++)
//        {
//            cin >> num[i];
//        }
//        dp[0] = num[0];
//        for (int i = 1; i < n; i++)
//        {
//            for (int j = 0; j<i; j++)
//            {
//                if (num[i] > num[j])
//                    dp[i] = max(dp[i], dp[j] + num[i]);
//            }
//            dp[i] = max(dp[i], num[i]);
//        }
//        for (int i = 0; i<n; i++)
//        {
//            Max = max(Max, dp[i]);
//        }
//        cout << Max << endl;
//    }
//    return 0;
//}



/*
Max Sum
calculate the max sum of a sub-sequence
*/
int main()
{
    int i, Case = 1, t, start, end, n, pos, now, before, max;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (i = 1; i <= n; i++)
        {
            cin >> now;
            if (i == 1)
            {
                max = before = now;  
                pos = start = end = 1;
            }
            else
            {
                if (now > now + before)
                {
                    before = now;
                    pos = i;
                }
                else
                    before += now;
            }
            if (before > max)
            {
                max = before;
                start = pos;
                end = i;
            }    
        }
        printf_s("Case %d:
%d %d %d
", Case++, max, start, end);
        printf_s("
");
    }
    return 0;
}