这是一道稍微有点难度的动态规划题.
首先可以想到的做法是枚举每个区间的和, 预处理 sum[i]来表示区间 [1, i] 的和之后通过减法我们可以 O(1)时间获得区间 [i, j] 的和, 因此这个做法的时间复杂度为 O(n^2).
然后这题的数据范围较大, 因此还需作进一步优化才可以 AC. 记第 i 个元素为 a[i], 定义 dp[i]表示以下标 i 结尾的区间的最大和, 那么 dp[i]的计算有 2 种选择, 一种是含有 a[i-1], 一种是不含有 a[i-1], 前者的最大值为 dp[i-1]+a[i], 后者的最大值为 a[i]. 而两者取舍的区别在于 dp[i-1]是否大于 0.
- #include <stdio.h>
- #include <string.h>
- #include <iostream>
- #include <string>
- #include <math.h>
- #include <algorithm>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <set>
- #include <map>
- #include <sstream>
- const int INF=0x3f3f3f3f;
- typedef long long LL;
- const int mod=1e9+7;
- //const double PI=acos(-1);
- #define Bug cout<<"---------------------"<<endl
- const int maxn=1e5+10;
- using namespace std;
- int A[maxn];
- int dp[maxn];
- int main()
- {
- int n;
- while(~scanf("%d",&n)&&n)
- {
- int ml=1,mr=n,MAX=0,l,r;
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&A[i]);
- if(A[i]>MAX)
- {
- MAX=A[i];
- ml=mr=i;
- }
- }
- for(int i=1;i<=n;i++)
- {
- if(A[i]>dp[i-1]+A[i])
- {
- l=i;
- dp[i]=A[i];
- }
- else
- {
- dp[i]=dp[i-1]+A[i];
- if(dp[i]>MAX)
- {
- MAX=dp[i];
- ml=l;
- mr=i;
- }
- }
- }
- printf("%d %d %d\n",MAX,A[ml],A[mr]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3264631.html