Best Time to Buy and Sell Stock II In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement: Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the i-th day.

You can buy and sell the stock as many times as you like (i.e., multiple transactions are allowed). However, you must sell the stock before you buy again.

Return the maximum profit you can achieve.

Example:

• Input: [7, 1, 5, 3, 6, 4]
• Output: 7
  • Explanation: Buy at day 2 (price = 1), sell at day 3 (price = 5). Profit = 5 – 1 = 4.
  • Then buy at day 4 (price = 3), sell at day 5 (price = 6). Profit = 6 – 3 = 3.
  • Total profit = 4 + 3 = 7.
• Input: [1, 2, 3, 4, 5]
• Output: 4
  • Explanation: Buy at day 1 (price = 1), sell at day 5 (price = 5). Profit = 5 – 1 = 4.
• Input: [7, 6, 4, 3, 1]
• Output: 0
  • Explanation: No transactions are done, so the profit is 0.

Approach

In this case, multiple transactions are allowed. A straightforward solution is to buy and sell the stock whenever there is a price increase, since each increase provides an opportunity for profit.

1. Greedy Approach:
   • We can add the profit whenever the price on the current day is higher than the price on the previous day. This simulates buying and selling at every price rise.
   • Essentially, we calculate the profit as the sum of all positive price differences from one day to the next.
2. Optimal Solution:
   • Instead of tracking individual buy and sell prices, we simply look for local price increases and accumulate the profits.

Code Implementation

---

C:

#include <stdio.h>

int maxProfit(int* prices, int pricesSize) {
    int max_profit = 0;

    for (int i = 1; i < pricesSize; i++) {
        if (prices[i] > prices[i - 1]) {
            max_profit += prices[i] - prices[i - 1]; // add the profit from price increase
        }
    }

    return max_profit;
}

int main() {
    int prices[] = {7, 1, 5, 3, 6, 4};
    int pricesSize = sizeof(prices) / sizeof(prices[0]);
    printf("Max profit: %d\n", maxProfit(prices, pricesSize));  // Output: 7
    return 0;
}

---

C++:

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

int maxProfit(vector<int>& prices) {
    int max_profit = 0;

    for (int i = 1; i < prices.size(); i++) {
        if (prices[i] > prices[i - 1]) {
            max_profit += prices[i] - prices[i - 1]; // add the profit from price increase
        }
    }

    return max_profit;
}

int main() {
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    cout << "Max profit: " << maxProfit(prices) << endl;  // Output: 7
    return 0;
}

---

Java:

public class BestTimeToBuyAndSellStockII {
    public static int maxProfit(int[] prices) {
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1]; // add the profit from price increase
            }
        }

        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println("Max profit: " + maxProfit(prices));  // Output: 7
    }
}

---

Python:

def maxProfit(prices):
    max_profit = 0

    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            max_profit += prices[i] - prices[i - 1]  # add the profit from price increase

    return max_profit

# Example usage
prices = [7, 1, 5, 3, 6, 4]
print("Max profit:", maxProfit(prices))  # Output: 7

---

C#:

using System;

public class BestTimeToBuyAndSellStockII {
    public static int MaxProfit(int[] prices) {
        int maxProfit = 0;

        for (int i = 1; i < prices.Length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1]; // add the profit from price increase
            }
        }

        return maxProfit;
    }

    static void Main() {
        int[] prices = {7, 1, 5, 3, 6, 4};
        Console.WriteLine("Max profit: " + MaxProfit(prices));  // Output: 7
    }
}

---

JavaScript:

function maxProfit(prices) {
    let maxProfit = 0;

    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            maxProfit += prices[i] - prices[i - 1]; // add the profit from price increase
        }
    }

    return maxProfit;
}

// Example usage
let prices = [7, 1, 5, 3, 6, 4];
console.log("Max profit:", maxProfit(prices));  // Output: 7

---

Explanation:

1. Greedy Approach:
   • We iterate through the prices array from the second element to the last.
   • Whenever we find that the current price is greater than the previous day’s price (prices[i] > prices[i - 1]), we calculate the profit by subtracting the previous day’s price from the current price and add it to maxProfit.
   • This way, we capture all the opportunities where the stock price rises and accumulate the profits.
2. Example Walkthrough:
   • Input: [7, 1, 5, 3, 6, 4]
   • Day 1 to Day 2: Price falls, no transaction.
   • Day 2 to Day 3: Buy at 1, sell at 5 → Profit = 5 – 1 = 4.
   • Day 3 to Day 4: Price falls, no transaction.
   • Day 4 to Day 5: Buy at 3, sell at 6 → Profit = 6 – 3 = 3.
   • Day 5 to Day 6: Price falls, no transaction.
   • Total profit = 4 + 3 = 7.
3. Time Complexity:
   • O(n) where n is the number of days (or the length of the prices array). We only iterate through the array once.
4. Space Complexity:
   • O(1) since we only need a few variables (maxProfit) to store intermediate results, and no additional data structures are required.

---

Summary:

This problem can be efficiently solved using a greedy approach, where we accumulate profits from each price increase. This approach runs in O(n) time and uses O(1) space, making it optimal for this problem. It works well when multiple transactions are allowed, as we can capture all upward price movements.