软文网站,黑龙江新闻联播直播今天视频,wordpress seo 插件,破解空间网站股票买卖
题目
阿福该炒股了#xff0c;然后假设他已经预测到了后几天的股票#xff0c;要求他最多买卖两次的赚到的最大值。 #xff08;注#xff1a;他只有第一次卖了才能再买#xff09; 输入
3 7 5 14 -2 4 9 3 17 6 6 8 7 4 1 -2 4 18 9 5 2
输出
28 2…股票买卖
题目
阿福该炒股了然后假设他已经预测到了后几天的股票要求他最多买卖两次的赚到的最大值。 注他只有第一次卖了才能再买 输入
3 7 5 14 -2 4 9 3 17 6 6 8 7 4 1 -2 4 18 9 5 2
输出
28 2 0 解题思路
用f[i]表示从1到i天买一次的最优解fm[i]表示从第i天到第n天买一次的最优解然后枚举一下咯是的吧。 代码
#includecstdio
#includeiostream
#includecstring
using namespace std;
int t,a[100001],maxs,n,min1,max1,min2,max2;
int fm[100001],f[100001];
int main()
{scanf(%d,t);for (int ti1;tit;ti){memset(f,0,sizeof(f));memset(fm,0,sizeof(fm));//清零maxs0;scanf(%d,n);for (int i1;in;i){scanf(%d,a[i]);}maxsa[n];for (int in-1;i1;i--) {maxsmax(a[i],maxs);f[i]max(maxs-a[i],f[i1]);}//求fmaxsa[1];for (int i2;in;i) {maxsmin(a[i],maxs);fm[i]max(a[i]-maxs,fm[i-1]);}//求fmmaxs0;for (int i2;in;i){maxsmax(f[i]fm[i],maxs);}//求最大值printf(%d\n,max(a[2]-a[1],maxs));}
} Maximum sum
题目
求两个不重复的子段和让他最大 输入
1
10 1 -1 2 2 3 -3 4 -4 5 -5
输出
13 解题思路
同上 用f[i]表示从1到i个的最大子段和fm[i]表示从第i个到第n个的最大子段和然后枚举一下咯是的吧。 代码
#includecstdio
#includeiostream
#includecstring
using namespace std;
int
t,n,mins,f[50002],s[50002],fm[50002],a[50002];
int main()
{scanf(%d,t);for (int ti1;tit;ti){memset(f,0,sizeof(f));memset(fm,0,sizeof(fm));memset(s,0,sizeof(s));scanf(%d,n);for (int i1;in;i){scanf(%d,a[i]);s[i]s[i-1]a[i];}f[1]a[1];minsmin(s[1],0);for (int i2;in;i){f[i]max(fm[i-1],s[i]-mins);minsmin(s[i],mins);}//求ffor (int in;i1;i--){s[i]s[i1]a[i];}fm[n]a[n];minsmin(s[n],0);for (int in-1;i1;i--){fm[i]max(fm[i1],s[i]-mins);minsmin(s[i],mins);}//求fmmins-23333333;for (int i1;in;i){minsmax(mins,f[i]fm[i1]);}//求最大值printf(%d\n,mins);}
}
