Bài 2: Best Time to Buy and Sell Stock

Đề bài

Cho mảng prices[] chứa giá cổ phiếu theo thứ tự thời gian.

Tính lợi nhuận tối đa với 1 lần mua và 1 lần bán, phải mua trước khi bán.

Yêu cầu: Chỉ dùng for, không dùng LINQ/third-party.

Phân tích

Input/Output

Input:  [7, 1, 5, 3, 6, 4]
Output: 5
Giải thích: Mua ngày 2 (giá 1), bán ngày 5 (giá 6) → 6 - 1 = 5

Edge cases

• Mảng rỗng → 0
• 1 phần tử → 0 (không thể bán)
• Giá giảm liên tục → 0 (không giao dịch)
• Null array → Exception

Solution

Final Version - Simple & Optimal

public static class StockProfitSolver
{
    /// <summary>
    /// Tính lợi nhuận tối đa với 1 lần mua-bán
    /// Time: O(n), Space: O(1)
    /// </summary>
    /// <returns>Lợi nhuận tối đa, hoặc 0 nếu không có lợi nhuận</returns>
    public static int CalculateMaxProfit(int[] prices)
    {
        if (prices == null)
            throw new ArgumentNullException(nameof(prices));
        
        if (prices.Length < 2)
            return 0;
        
        int minPrice = int.MaxValue;
        int maxProfit = 0;
        
        for (int i = 0; i < prices.Length; i++)
        {
            // Update minimum price seen so far
            if (prices[i] < minPrice)
            {
                minPrice = prices[i];
            }
            // Calculate profit if selling today
            else if (prices[i] - minPrice > maxProfit)
            {
                maxProfit = prices[i] - minPrice;
            }
        }
        
        return maxProfit;
    }
    
    /// <summary>
    /// Tính lợi nhuận với thông tin chi tiết (buy/sell days)
    /// </summary>
    public static (int profit, int buyDay, int sellDay) CalculateMaxProfitWithDetails(int[] prices)
    {
        if (prices == null)
            throw new ArgumentNullException(nameof(prices));
        
        if (prices.Length < 2)
            return (0, -1, -1);
        
        int minPrice = int.MaxValue;
        int maxProfit = 0;
        int bestBuyDay = -1;
        int bestSellDay = -1;
        int currentBuyDay = 0;
        
        for (int i = 0; i < prices.Length; i++)
        {
            if (prices[i] < minPrice)
            {
                minPrice = prices[i];
                currentBuyDay = i;
            }
            else if (prices[i] - minPrice > maxProfit)
            {
                maxProfit = prices[i] - minPrice;
                bestBuyDay = currentBuyDay;
                bestSellDay = i;
            }
        }
        
        return (maxProfit, bestBuyDay, bestSellDay);
    }
}

Usage

// Basic usage
int[] prices = { 7, 1, 5, 3, 6, 4 };
int profit = StockProfitSolver.CalculateMaxProfit(prices);
// profit = 5

// With details
var (profit, buyDay, sellDay) = StockProfitSolver.CalculateMaxProfitWithDetails(prices);
// profit = 5, buyDay = 1, sellDay = 4
Console.WriteLine($"Mua ngày {buyDay} (giá {prices[buyDay]}), bán ngày {sellDay} (giá {prices[sellDay]})");

// Edge cases
StockProfitSolver.CalculateMaxProfit(new int[] { 7, 6, 4, 3, 1 }); // 0
StockProfitSolver.CalculateMaxProfit(new int[] { 1 }); // 0
StockProfitSolver.CalculateMaxProfit(Array.Empty<int>()); // 0

Unit Tests

using Xunit;

public class StockProfitSolverTests
{
    [Fact]
    public void CalculateMaxProfit_Example1_Returns5()
    {
        int[] prices = { 7, 1, 5, 3, 6, 4 };
        int profit = StockProfitSolver.CalculateMaxProfit(prices);
        Assert.Equal(5, profit);
    }
    
    [Fact]
    public void CalculateMaxProfit_DecreasingPrices_Returns0()
    {
        int[] prices = { 7, 6, 4, 3, 1 };
        int profit = StockProfitSolver.CalculateMaxProfit(prices);
        Assert.Equal(0, profit);
    }
    
    [Fact]
    public void CalculateMaxProfit_IncreasingPrices_ReturnsMaxDifference()
    {
        int[] prices = { 1, 2, 3, 4, 5 };
        int profit = StockProfitSolver.CalculateMaxProfit(prices);
        Assert.Equal(4, profit);
    }
    
    [Fact]
    public void CalculateMaxProfit_NullArray_ThrowsException()
    {
        Assert.Throws<ArgumentNullException>(() => 
            StockProfitSolver.CalculateMaxProfit(null));
    }
    
    [Fact]
    public void CalculateMaxProfit_SingleElement_Returns0()
    {
        int[] prices = { 5 };
        int profit = StockProfitSolver.CalculateMaxProfit(prices);
        Assert.Equal(0, profit);
    }
    
    [Fact]
    public void CalculateMaxProfitWithDetails_ReturnsCorrectDays()
    {
        int[] prices = { 7, 1, 5, 3, 6, 4 };
        var (profit, buyDay, sellDay) = StockProfitSolver.CalculateMaxProfitWithDetails(prices);
        
        Assert.Equal(5, profit);
        Assert.Equal(1, buyDay);
        Assert.Equal(4, sellDay);
        Assert.Equal(1, prices[buyDay]);
        Assert.Equal(6, prices[sellDay]);
    }
    
    [Fact]
    public void CalculateMaxProfitWithDetails_NoProfit_ReturnsNegativeDays()
    {
        int[] prices = { 5, 4, 3, 2, 1 };
        var (profit, buyDay, sellDay) = StockProfitSolver.CalculateMaxProfitWithDetails(prices);
        
        Assert.Equal(0, profit);
        Assert.Equal(-1, buyDay);
        Assert.Equal(-1, sellDay);
    }
}

Mở rộng 1: Multiple Transactions

Đề: Được mua-bán nhiều lần, nhưng phải bán trước khi mua lại.

public static class MultipleTransactionSolver
{
    /// <summary>
    /// Unlimited transactions - Buy at every valley, sell at every peak
    /// Time: O(n), Space: O(1)
    /// </summary>
    public static int CalculateMaxProfit(int[] prices)
    {
        if (prices == null || prices.Length < 2)
            return 0;
        
        int totalProfit = 0;
        
        for (int i = 1; i < prices.Length; i++)
        {
            // If price increases, capture the profit
            if (prices[i] > prices[i - 1])
            {
                totalProfit += prices[i] - prices[i - 1];
            }
        }
        
        return totalProfit;
    }
}

// Usage
int[] prices = { 7, 1, 5, 3, 6, 4 };
// Buy at 1, sell at 5: +4
// Buy at 3, sell at 6: +3
// Total: 7
int profit = MultipleTransactionSolver.CalculateMaxProfit(prices); // 7

// Test
[Fact]
public void MultipleTransactions_Example_Returns7()
{
    int[] prices = { 7, 1, 5, 3, 6, 4 };
    int profit = MultipleTransactionSolver.CalculateMaxProfit(prices);
    Assert.Equal(7, profit);
}

Mở rộng 2: Maximum K Transactions

Đề: Tối đa K lần giao dịch.

public static class KTransactionSolver
{
    /// <summary>
    /// Maximum K transactions - Dynamic Programming
    /// Time: O(kn), Space: O(kn)
    /// </summary>
    public static int CalculateMaxProfit(int[] prices, int k)
    {
        if (prices == null || prices.Length < 2 || k <= 0)
            return 0;
        
        int n = prices.Length;
        
        // If k >= n/2, we can do unlimited transactions
        if (k >= n / 2)
        {
            return MultipleTransactionSolver.CalculateMaxProfit(prices);
        }
        
        // DP: dp[t, d] = max profit with at most t transactions until day d
        int[,] dp = new int[k + 1, n];
        
        for (int t = 1; t <= k; t++)
        {
            int maxDiff = -prices[0];
            
            for (int d = 1; d < n; d++)
            {
                dp[t, d] = Math.Max(dp[t, d - 1], prices[d] + maxDiff);
                maxDiff = Math.Max(maxDiff, dp[t - 1, d] - prices[d]);
            }
        }
        
        return dp[k, n - 1];
    }
}

// Test
[Fact]
public void KTransactions_TwoTransactions_Returns6()
{
    // [3, 3, 5, 0, 0, 3, 1, 4]
    // Buy at 3, sell at 5: +2
    // Buy at 0, sell at 4: +4
    // Total: 6
    int[] prices = { 3, 3, 5, 0, 0, 3, 1, 4 };
    int profit = KTransactionSolver.CalculateMaxProfit(prices, 2);
    Assert.Equal(6, profit);
}

Mở rộng 3: Transaction Fee

Đề: Mỗi lần bán phải trả fee.

public static class StockProfitWithFeeSolver
{
    /// <summary>
    /// Calculate max profit with transaction fee for each sell
    /// Time: O(n), Space: O(1)
    /// </summary>
    public static int CalculateMaxProfit(int[] prices, int fee)
    {
        if (prices == null || prices.Length < 2)
            return 0;
        
        // cash: max profit if we don't hold stock
        // hold: max profit if we hold stock
        int cash = 0;
        int hold = -prices[0];
        
        for (int i = 1; i < prices.Length; i++)
        {
            // Sell or keep not holding
            cash = Math.Max(cash, hold + prices[i] - fee);
            
            // Buy or keep holding
            hold = Math.Max(hold, cash - prices[i]);
        }
        
        return cash;
    }
}

// Test
[Fact]
public void WithFee_Example_Returns4()
{
    // [1, 3, 2, 8, 4, 9], fee = 2
    // Buy at 1, sell at 8: 8 - 1 - 2 = 5
    // Buy at 4, sell at 9: 9 - 4 - 2 = 3
    // But optimal: Buy at 1, sell at 8 = 5
    int[] prices = { 1, 3, 2, 8, 4, 9 };
    int profit = StockProfitWithFeeSolver.CalculateMaxProfit(prices, 2);
    Assert.Equal(8, profit); // Buy at 1, sell at 8: 7, then buy at 4, sell at 9: 3 = 8
}

Tóm tắt

So sánh các versions

Design Decisions

Performance

Single transaction:
- Time: O(n) - 1 vòng lặp
- Space: O(1) - chỉ variables

Multiple transactions:
- Time: O(n) - 1 vòng lặp  
- Space: O(1)

K transactions:
- Time: O(k * n) - nested loops
- Space: O(k * n) - DP table

Best Practices (vừa đủ)

✅ Single responsibility
✅ Meaningful names
✅ XML comments
✅ Guard clauses
✅ Unit tests
❌ KHÔNG: Over-engineering

← Bài 1: Linear Equation | Quay lại Thuật toán & Giải thuật