动态规划:最大子串和

 

 
题目链接(点击直达)

 

问题 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 }
上一篇:12道Python字符编码和数据类型练习题


下一篇:LeetCode 33.搜索旋转排序数组