动态规划:最大子串和
2020-01-30 16:01:37来源:博客园 阅读 ()
动态规划:最大子串和
题目链接(点击直达)
问题 B: X额宝
时间限制: 1 Sec 内存限制: 256 MB提交: 46 解决: 33
[状态] [提交] [命题人:外部导入]
题目描述
【理财有风险,投资需谨慎】Alice计划将自己的所有红包拿去投资。
在粗略预测了该理财产品的各日收益后,Alice希望通过一次买卖获得最大的收益。
买卖当天均可以享受到当日盈亏,允许一天内先买后卖。
希望你帮她计算一下最大盈利。
输入
第一行是样例个数K(1<=K<=100)每个样例的第一行是天数N(1<=N<=100)
第二行包含N个整数Ai(-100<=Ai<=100),表示当天盈亏。
输出
对于每个样例,输出一个数字表示Alice的最大盈利。如果该理财产品赚不到钱,她也可以选择不购入此产品,请直接输出0。
样例输入
4 3 1 0 0 9 -2 1 -3 4 -1 2 1 -5 4 6 -4 -1 5 -4 1 -1 3 -9 -9 -6
样例输入
1 6 5 0
原理:先定义一个dp的数组变量,以n为长度,从dp[1]开始进行一次for循环(ps:如果从0开始会导致数组越界),利用max函数判断是当前的a[i]大还是上一个dp加上当前的a[i]之和大,即max(a[i],dp[i-1]+a[i]);找出两者中较大的一个,作为当前dp[i]中的内容。
之后再做一次i从0到9的for循环,找出最终最大的一个和。
伪代码:
for(i=1;i<n;i++)
{
dp[i]=max(a[i]+dp[i-1]+a[i]);
}
int m=dp[0];
for(i=0;i<n;i++)
{
m=max(m,dp[i]);
}
C++代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int k,i,n,j; 6 scanf("%d",&k); 7 for(i=0;i<k;i++) 8 { 9 scanf("%d",&n); 10 int a[n]={0},dp[n]={0}; 11 for(j=0;j<n;j++) 12 { 13 scanf("%d",&a[j]); 14 } 15 int l; 16 dp[0]=a[0]; 17 for(l=1;l<n;l++) 18 { 19 dp[l]=max(a[l],dp[l-1]+a[l]); 20 } 21 int m=dp[0]; 22 for(j=0;j<n;j++) 23 { 24 m=max(m,dp[j]); 25 } 26 if(m>0) 27 printf("%d\n",m); 28 else 29 { 30 printf("0\n"); 31 } 32 } 33 }
原文链接:https://www.cnblogs.com/jackwang-sparrow/p/12244107.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:结题报告
下一篇:一本通1166 求f(x,n)
- 最长回文子串 2020-04-13
- 无重复字符的最长子串 2020-04-08
- [题记-动态规划] 编辑距离 - leetcode 2020-04-06
- 关于 DP 的一些内容 2019-12-25
- 最小割最大流定理&残量网络的性质 2019-12-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash