Description:
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Examples:
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.
Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.Solution in Python:
Python
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# Initialize the total profit to 0
total_profit = 0
# Iterate through the list of prices from the second day to the last day
for i in range(1, len(prices)):
# Calculate the difference between the current day's price and the previous day's price
profit = prices[i] - prices[i - 1]
# If the difference is positive, add it to the total profit
# This means we buy on the previous day and sell on the current day
if profit > 0:
total_profit += profit
# Return the total profit accumulated
return total_profitExplanation
- Initialization:
total_profitis initialized to 0. This variable will accumulate the total profit from all profitable transactions.
- Iterating through prices:
- A
forloop starts from the second day (i = 1) to the last day of thepriceslist. We start from the second day because we need to compare each day with the previous day.
- A
- Calculating daily profit:
- For each day
i, the profit is calculated as the difference between the price on dayiand the price on dayi-1.
- For each day
- Adding positive profits:
- If the calculated profit is positive (
profit > 0), it means that buying on the previous day and selling on the current day is profitable. This profit is added tototal_profit.
- If the calculated profit is positive (
- Returning the result:
- After the loop completes, the accumulated
total_profitis returned as the maximum profit that can be achieved.
- After the loop completes, the accumulated
Constraints
- The function will handle arrays with a length between 1 and 30,000.
- Each price in the array is between 0 and 10,000.
This approach efficiently calculates the maximum profit in O(n) time complexity, where n is the length of the prices array.
Solution in Javascript:
JavaScript
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
// Initialize the total profit to 0
let totalProfit = 0;
// Iterate through the list of prices from the second day to the last day
for (let i = 1; i < prices.length; i++) {
// Calculate the difference between the current day's price and the previous day's price
let profit = prices[i] - prices[i - 1];
// If the difference is positive, add it to the total profit
// This means we buy on the previous day and sell on the current day
if (profit > 0) {
totalProfit += profit;
}
}
// Return the total profit accumulated
return totalProfit;
};Solution in Java:
Java
class Solution {
public int maxProfit(int[] prices) {
// Initialize the total profit to 0
int totalProfit = 0;
// Iterate through the list of prices from the second day to the last day
for (int i = 1; i < prices.length; i++) {
// Calculate the difference between the current day's price and the previous day's price
int profit = prices[i] - prices[i - 1];
// If the difference is positive, add it to the total profit
// This means we buy on the previous day and sell on the current day
if (profit > 0) {
totalProfit += profit;
}
}
// Return the total profit accumulated
return totalProfit;
}
}Solution in C#:
C#
public class Solution {
public int MaxProfit(int[] prices) {
// Initialize the total profit to 0
int totalProfit = 0;
// Iterate through the list of prices from the second day to the last day
for (int i = 1; i < prices.Length; i++) {
// Calculate the difference between the current day's price and the previous day's price
int profit = prices[i] - prices[i - 1];
// If the difference is positive, add it to the total profit
// This means we buy on the previous day and sell on the current day
if (profit > 0) {
totalProfit += profit;
}
}
// Return the total profit accumulated
return totalProfit;
}
}