dp / greedy

类似贪心的思想。

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <queue>

#define endl "\n"
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
#define ULL unsigned long long
#define INF 0x3f
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define mid(a, b) (a + b) >> 1 

const int N = 1e5 + 7, M = 1e3 + 9, P = 131, MOD = 1e6 + 7;

using namespace std;	

inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if(c == '-') flag = true;
    else num = c - '0';
    while(isdigit(c = getchar())) num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
} 

int t, idx;

int n, res, s, l, r, st;

int f[N];

void init()

{
	n = read();
	for (int i = 1; i <= n; i ++ ) f[i] = read();
	l = r = st = 1;
	res = f[1];
}

void solve()

{
	init();
	
	
	for (int i = 2; i <= n; i ++ )
	{
		if (f[i - 1] >= 0) f[i] += f[i - 1];
		else st = i;
		if (f[i] > res) res = f[i], l = st, r = i;
	}
	if (idx) cout << endl;
	cout << "Case " << ++ idx << ":" << endl;
	cout << res << " " << l << " " << r << endl;
	//puts("");
}

signed main()

{
	IOS;
	
	t = 1;
	t = read();
	while (t -- ) solve();
}