求一段数列的最大连续子序列和,然后让你输出三个数字,
分别是该段数列的最大连续子序列和的值,最大连续子序列第一个数的下标(下标从1开始),最大连续子序列最后一个数的下标。
思路
把数列第一个数存入dp[0].
状态转移方程,max( dp[i-1] + a[i] , a[i] )
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| #include <iostream> #include <cstdio> #include <string> #include <cstring> using namespace std;
int a[100005]; int dp[100005];
int main(){ int T; scanf("%d", &T); while(T--){ int n; scanf("%d", &n); for (int i = 0; i < n; i++){ scanf("%d", &a[i]); } dp[0] = a[0]; int start = 0, end = 0, max = -1001; int first = 0, last = 0; for (int i = 0; i < n; i++){ if(dp[i-1]+a[i]>=a[i]){ dp[i] = dp[i - 1] + a[i]; end = i; } else{ dp[i] = a[i]; start = end = i; } if(max<dp[i]){ max = dp[i]; first = start; last = end; } } printf("Case %d:\n%d %d %d\n", ++i, max, first+1, last+1); if(T!=0){ printf("\n"); } } return 0; }
|