免费的行情网站app软件大全,网络运维工程师面试题,竞价排名点击器,庆阳网站设计费用参考资料#xff1a;《算法竞赛》#xff0c;罗勇军 郭卫斌 著 本博客作为阅读本书的学习笔记#xff0c;仅供交流学习。 建议关注 罗勇军老师博客 3. 单调队列与最大子序和问题
不限制子序列长度问题——贪心法或动态规划
HDOJ 1003 MAX SUM Max Sum Time Limit: 2000/10… 参考资料《算法竞赛》罗勇军 郭卫斌 著 本博客作为阅读本书的学习笔记仅供交流学习。 建议关注 罗勇军老师博客 3. 单调队列与最大子序和问题
不限制子序列长度问题——贪心法或动态规划
HDOJ 1003 MAX SUM Max Sum Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Problem Description Given a sequence a[1],a[2],a[3]…a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 (-1) 5 4 14. Input The first line of the input contains an integer T(1T20) which means the number of test cases. Then T lines follow, each line starts with a number N(1N100000), then N integers followed(all the integers are between -1000 and 1000). Output For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases. Sample Input 2 5 6 -1 5 4 -7 7 0 6 -1 1 -6 7 -5 Sample Output Case 1: 14 1 4 Case 2: 7 1 6 Author Ignatius.L 贪心法
#include bits/stdc.h
using namespace std;
const int INF 0x7fffffff;int main() {int t; cint;//测试用例个数for (int i 1; i t; i) {int n; cinn;int maxsum -INF;//最大子序和初始设为一个最小的int负数int start 1, end1, p1; //起点终点扫描位置int sum0;for (int j 1; j n; j) {int a; cina; suma;//读入一个元素累加if (summaxsum){maxsumsum;startp;endj;}if (sum0){//扫描到j时若前面的最大子序和是负数从下一个重新开始求和sum0;pj1;}}printf(Case %d:\n,i);printf( %d %d %d\n,maxsum,start,end);if (i!t) coutendl;}return 0;
}动态规划
#include bits/stdc.h
using namespace std;
int dp[100005];//dp[i]:以第i个数为结尾的最大值
int main(){int t; cint;//测试用例个数for (int k 1; k t; k) {int n; cinn;for (int i 1; i n; i) cindp[i];//用dp[]存储数据a[]int start1, end1, p1;//起点终点扫描位置int maxsum dp[1];for (int i 2; i n; i) {if (dp[i-1]dp[i]dp[i])//转移方程dp[i]max(dp[i-1]a[i],a[i])dp[i]dp[i-1]dp[i];//dp[i-1]a[i]比a[i]大else pi;//a[i]更大则dp[i]a[i]if (dp[i]maxsum){//dp[i]更大maxsumdp[i];startp;endi;//p开始i结尾}}printf(Case %d:\n,k);printf( %d %d %d\n,maxsum,start,end);if (k!t) coutendl;}return 0;
}
限制子序列长度问题——单调队列
#include bits/stdc.h
using namespace std;
dequeint dq;
int s[100005];
int main(){int n,m;scanf(%d %d,n,m);for (int i 1; i n; i) scanf(%lld,s[i]);for (int i 1; i n; i) s[i]s[i-1]s[i];//计算前缀和int ans -1e8;dq.push_back(0);for (int i 1; i n; i) {while(!dq.empty()dq.front()i-m) dq.pop_front();//队头超过m范围删头if (dq.empty()) ans max(ans,s[i]);else ans max(ans,s[i]-s[dq.front()]);//队头就是最小的s[k]while(!dq.empty()s[dq.back()]s[i]) dq.pop_back();//队尾大于s[i]:去尾dq.push_back(i);}printf(%d\n,ans);return 0;
}
