i번째 요소가 i일의 주어진 주식 가격인 배열이 있다고 가정합니다. 우리는 최대 이익을 찾는 알고리즘을 고안해야 합니다. 최대 k개의 트랜잭션을 완료할 수 있습니다. 따라서 입력이 [3,2,6,4,0,3]이고 k =2인 경우 출력은 7이 됩니다. =6), 이익은 6-2 =4가 됩니다. 그런 다음 5일째에 매수(가격은 0), 6일째에 매도(가격은 3), 이익은 3-0 =3이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
N + 5 x N + 5 x 2 차수의 3D 배열을 정의합니다.
-
pre()
라는 메소드를 정의하십시오. -
i를 초기화하기 위해 :=0, i<=N일 때 i를 1만큼 증가 do -
-
j를 초기화하기 위해 :=0, j<=N일 때 j를 1만큼 증가 do -
-
dp[i, j, 1] :=- 1, dp[i, j, 0] :=- 1
-
-
-
solve()라는 메소드를 정의하면 arr, i, n, k 및 status가 필요합니다.
-
i가 n과 같으면
-
상태가 0이 아닌 경우
-
반환 - 100000
-
-
0 반환
-
-
dp[i, k, status]가 -1과 같지 않으면
-
반환 dp[i, k, 상태]
-
-
ans :=해결(arr,i + 1,n,k,상태)
-
상태가 0이 아닌 경우
-
ans :=ans의 최대값, solve(arr,i + 1,n,k - 1, 상태의 역수) + arr[i]
-
-
그렇지 않으면 -
-
k>0이면
-
ans :=최대 ans,solve(arr,i + 1,n,k, 상태 상태의 역수) - arr[i]
-
-
-
return dp[i, k, status] :=ans
-
주요 방법에서 다음을 수행하십시오 -
-
pre()
함수 호출 -
k>=가격의 크기 /2이면,
-
답변 :=0
-
i를 초기화하기 위해 :=1, i <가격의 크기일 때 i 를 1 증가 -
-
가격[i]> 가격[i-1]이면, as =as + 가격[i] - 가격[i - 1]
-
-
반환
-
-
반환 해결(가격, 0, 가격의 크기, k, 0)
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
typedef int lli;
const lli N = 1000;
lli dp[N + 5][N + 5][2];
class Solution {
public:
void pre(){
for(lli i =0;i<=N;i++){
for(lli j = 0;j<=N;j++){
dp[i][j][1]=-1;
dp[i][j][0]=-1;
}
}
}
lli solve(vector<int> &arr, lli i,lli n,lli k, lli status){
if(i == n){
if(status)return -100000;
return 0;
}
if(dp[i][k][status]!=-1)return dp[i][k][status];
lli ans = solve(arr, i+1,n,k,status);
if(status){
ans = max(ans,solve(arr,i+1,n,k-1,!status)+ arr[i]) ;
} else {
if(k>0){
ans = max(ans,(lli)solve(arr,i+1,n,k,!status)- arr[i]) ;
}
}
return dp[i][k][status] = ans;
}
int maxProfit(int k, vector<int>& prices) {
pre();
if(k>=prices.size()/2){
int ans = 0;
for(int i = 1; i < prices.size(); i++){
if(prices[i] > prices[i-1])ans += prices[i] - prices[i-1];
}
return ans;
}
return solve(prices,0,prices.size(),k,0);
}
};
main(){
Solution ob;
vector<int> v = {3,2,6,4,0,3};
cout << (ob.maxProfit(2, v));
} 입력
{ 3,2,6,4,0,3} 출력
7