Best Time to Buy and Sell Stock II You are given a...

Question

Best Time to Buy and Sell Stock II
You are given an integer array prices, where priceslil is the price of a stock on the i-th day, and an integer K.
You may perform as many transactions as you like, subject to the following rules:
• If you buy a stock on day i, you must sell it pxactly K days later, on day i + K. You cannot sell earlier or later.
• You may hold at most one share at any time.
Therefore, after buying on day i, you cannot buy another share until the current share is sold on day i + K.
• After selling a share on day i + K, you may immediately buy another share on the same day.
Determine the maximum total profit that can be achieved
ishsheikhh
Input Format
The first line contains a integer, N, denoting the number of days.
The second line contains a integer, K, denoting the required holding period.
Each line i of the N subsequent lines (where 0 ≤ i<
N) contains a integer, prices|i).
Constraints
1 <= N <= 10^4
1<= K<=N
0 <= prices[i] < = 10^4
anishsheikhh
ishsheikh
Examples
EXAMPLE 1
Input:
6
2
124257
Output:
8
iddanis!?
Explanation:
N is 6, K is 2. The prices are 1 2 4 25 7.
On day 0, the price is 1. We buy the stock.
Because K is 2, we must sell exactly on day 2. The price on day 2 is 4. The profit for this trade is 3.
We can immediately buy again on day 2.We do not buy on day 2, but instead wait and buy on day 3 when the price is 2.
Because K is 2, we must sell exactly on day 5. The price on day 5 is 7. The profit for this trade is 5.
The total profit is 3 plus 5, which equals 8.
迥
EXAMPLE 2
Input:
6
326503
Output:
7
Explanation:
N is 6, K is 1. The prices are 3 2 65 0 3.
On day 1, the price is 2. We buy the stock.
Because K is 1, we must sell on day 2. The price on day 2 is 6. The profit is 4.
On day 4,
the price is 0. We buy the stock.
Because K is 1, we must sell on day 5. The price on day 5 is 3. The profit is 3.
The total profit is 4 plus 3, which equals 7.
EXAMPLE 3
Input:
543 21
Output:
0
Explanation:
N is 5, K is 2. The prices are 5 4 3 2 1.
The prices are strictly decreasing. Any transaction held for 2 days will result in a loss.
The optimal strategy is to do nothing, resulting in a maximum profit of 0.

#include <bits/stdc++.h› using namespace std;

v int solve(int N, int k, vector<int›& prices) {
5
6
7
// Write your solution here
10
11 v int main() {
12
13
ios_base: : sync with stdio(false);
14
cin.tie(NULL);
15
16
17
18
int N; cin >> N; int K; cin > K;
vector<int> prices(N);
for (int i = 0; i ‹ N; i+t) cin » prices(i);
19
20
21
22
auto result = solve(N, K, prices);
cout << result << endl; return 0;
Write a code in c++

Answer 1

cpp
#include <bits/stdc++.h>
using namespace std;

long long solve(int N, int K, const vector<int>& prices) {
    // dp[day] = maximum profit after completing all transactions
    // on or before this day.
    vector<long long> dp(N, 0);

    for (int day = K; day < N; ++day) {
        // Option 1: Do not sell a stock on this day.
        dp[day] = dp[day - 1];

        // Option 2: Buy on (day - K) and sell today.
        long long currentProfit =
            static_cast<long long>(prices[day]) - prices[day - K];

        // A previous transaction may end on the same day this one begins.
        long long previousProfit = dp[day - K];

        dp[day] = max(dp[day], previousProfit + currentProfit);
    }

    return dp[N - 1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    vector<int> prices(N);
    for (int i = 0; i < N; ++i) {
        cin >> prices[i];
    }

    cout << solve(N, K, prices) << '\n';
    return 0;
}

Approach

For every possible selling day day, there are two choices:

Do not complete a transaction on that day, keeping dp[day - 1].
Buy on day - K and sell on day.

The second choice gives:

text
dp[day - K] + prices[day] - prices[day - K]

Using dp[day - K] allows a previous stock to be sold and a new stock to be bought on the same day, as permitted.

Time complexity: O(N)
Space complexity: O(N)

Best Time to Buy and Sell Stock II You are given a...

问题

思考

回答

Approach

分享这个问答