股票买卖III

本文主要是介绍股票买卖III，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

时间限制：1秒        内存限制：128M

题目描述
给定一个长度为�N的数组，数组中的第 i 个数字表示一个给定股票在第�i天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入格式
第一行包含整数�N，表示数组长度。

第二行包含�N个不大于10910​9​​的正整数，表示完整的数组。

输出格式
输出一个整数，表示最大利润。

数据范围
1≤�≤1051≤N≤10​5​​

样例输入

1. 8
2. 3 3 5 0 0 3 1 4

样例输出

1. 6

#include<cmath>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N],dp[N][3][3],n;
int main() {cin>>n;for(int i=1;i<=n;i++){cin>>a[i];} memset(dp,-0x3f,sizeof(dp));for(int i=0;i<=n;i++){dp[i][0][0]=0;}for(int i=1;i<=n;i++){for(int j=1;j<=2;j++ ){dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+a[i]);dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-a[i]);}}int  maxx;maxx=max(dp[n][1][0],dp[n][2][0]);cout<<maxx;return 0;
}

这篇关于股票买卖III的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---