给定一个长度为 N 的数组,数组中的第 i 个数字表示一个给定股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润,你最多可以完成 k 笔交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。一次买入卖出合为一笔交易。
输入格式
第一行包含整数 N 和 k,表示数组的长度以及你可以完成的最大交易数量。
第二行包含 N 个不超过 10000 的正整数,表示完整的数组。
输出格式
输出一个整数,表示最大利润。
数据范围
1≤N≤105,
1≤k≤100
输入样例1:
``
3 2
2 4 1
输出样例1:
2
输入样例2:
6 2
3 2 6 5 0 3
输出样例2:
7
样例解释
样例1:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。
样例2:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。共计利润 4+3 = 7.
状态表示:f[i][j][0]表示从前i天 进行完 第j次交易后现在手中的钱数
f[i][j][1]表示从前i天 正在进行 第j次交易时现在手中的钱数
属性:钱数的最大值;
状态计算:
注意:从手中没有股票到手中有股票表示开始进行第j次交易;
f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+w[i]);
可以由手中没有股票的前一天进行完第j次交易的状态进行转移
也可以从手中有股票的前一天正在进行第j次交易的状态卖出股票进行转移;
f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-w[i]);
可以从手中有股票的前一天正在进行第j次交易的状态进行转移
也可以从手中没有股票的前一天正在进行第j-1次交易的状态买入股票进行转移;
初始化:从前i天进行完第0次交易后现在手中的钱数为0;
因为手中的钱数可能为负数,所以其他值初始化为负无穷;
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll N=1e5+520,M=110;
ll f[N][M][2],w[N];
int main()
{
ll n,m;
cin>>n>>m;
for(ll i=1;i<=n;i++)cin>>w[i];
memset(f,-0x3f,sizeof(f));
for(ll i=0;i<=n;i++)f[i][0][0]=0;
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++)
{
f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+w[i]);
f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-w[i]);
}
ll res=0;
for(ll i=1;i<=m;i++)res=max(res,f[n][i][0]);
cout<<res<<endl;
}