Buy And Sell Stock - C++ Solution

1. Introduction

In this post, we explore a common problem in financial computing and dynamic programming: maximizing profit from buying and selling stocks. Given future predictions of share prices and a limit on the number of transactions, the challenge is to find the maximum profit achievable under the constraint of completing each transaction before starting another.

Problem

Given a list of future predictions of share prices and a positive integer k, find the maximum profit that can be earned by buying and selling shares at most k times. You can only hold one share at a time, meaning a new transaction can only start after the previous one is complete.

2. Solution Steps

1. Use dynamic programming to store the maximum profit at each transaction and day.

2. Create a 2D array dp with k+1 rows (for transactions) and n columns (for days).

3. Calculate the maximum profit for each transaction by comparing the profit of selling on the current day with the maximum profit of previous transactions.

4. Iterate through each day and transaction to fill the dp array.

5. Return the maximum profit from dp[k][n-1].

3. Code Program

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxProfit(vector<int>& prices, int k) {
    if (prices.empty() || k == 0) return 0;
    int n = prices.size();
    vector<vector<int>> dp(k + 1, vector<int>(n, 0));

    for (int i = 1; i <= k; i++) {
        int maxDiff = -prices[0];
        for (int j = 1; j < n; j++) {
            dp[i][j] = max(dp[i][j - 1], prices[j] + maxDiff);
            maxDiff = max(maxDiff, dp[i - 1][j] - prices[j]);
        }
    }

    return dp[k][n - 1];
}

int main() {
    vector<int> prices = {2, 4, 7, 5, 4, 3, 5};
    int k = 2;
    cout << "Maximum Profit: " << maxProfit(prices, k) << endl;
    return 0;
}

Output:

Maximum Profit: 7

Explanation:

The function maxProfit computes the maximum profit from buying and selling stocks at most k times. It uses a dynamic programming approach where dp[i][j] represents the maximum profit from at most i transactions up to day j. The algorithm iterates over each day, updating the maximum profit for each transaction level. For example, with the price array [2, 4, 7, 5, 4, 3, 5] and k = 2, the maximum profit is 7, achieved by buying at 2 and selling at 7, then buying at 3 and selling at 5.