Khi làm việc với Array, một trong những Data Structure phổ biến nhất trong nghề lập trình, có những bài toán hay ta có thể tham khảo và áp dụng vào thực tiễn, một trong số đó là Max Different Stock.

Bài toán này không khó, tuy nhiên cũng có thể tìm hiểu qua để biết thêm về một số trick làm việc với Array sao cho tối ưu.

Bắt đầu ngay thôi nào!

1. Bài toán

Given a list of stock prices for a company, find the maximum amount of money you could have made with one trade (one buy/sell).

Cho một danh sách giá cổ phiếu của công ty, tìm khoản lời lớn nhất có thể kiếm được nếu chỉ thực hiện một lệnh duy nhất (một lệnh mua / một lệnh bán)

Với input đầu vào cho bài toán Max Different Stock là [8,14,2,5,7,3,9,5], ta có thể vẽ được đồ thì như sau:

Yêu cầu của bài toán là với một lệnh mua và bán duy nhất, ta muốn tìm ra khoảng lời lớn nhất. Khoảng lời có thể hiểu là

• Mua 8, bán ra 14, lời 6
• Mua 2 bán ra 5 lời 3
• Mua 5 bán 9 lời 4
• ….

Một điểm nhỏ cần lưu ý là: lệnh mua phải đi trước lệnh bán. Không thể mua vào ở 2 và bán ra ở 8.

Vậy với đầu vào là một mảng a, danh sách giá cổ phiếu lên xuống theo thời gian, ta cần tìm ra khoản hời lớn nhất có thể kiếm được. Eww, bắt tay vào đi tìm lời giải thôi

2. Đi tìm lời giải cho Max Different Stock

Bước đầu tiên để giải quyết bài toán Max Different Stock, cần phải hiểu rằng giá trị mua bán có thể có index khác nhau (không kế tiếp.

Mua vào ở 2 có thể bán ra ở 9, không nhất thiết phải bán ra ở 5.

Tiến hành duyệt mảng từ đầu, dễ dàng có thể hiểu được ở vị trí i, phần tử a[i] sẽ có max_trade lớn nhất bằng chính a[i] trừ đi phần tử nhỏ nhất trước đó trong mảng.

max_trade[i] = a[i] - min_before_i

Maximum trade có thể kiếm được ở 5 là 3 (5-2). Do 8 > 5 và 14 > 5, nên sẽ không tính vào. Mua 14 mà bán 5 thì chắc chắn là lỗ cmnr. Từ chính ý tưởng này, ta có thể có hướng giải quyết theo hướng sau:

min_trade = 999 (hoặc dương vô cùng)
max_trade = 0
  for i : a
     // Tìm giá trị min nhỏ nhất phía trước a[i]
     min_trade = min(a[i], min_trade)
     // Max trade chính là khoảng cách giữa a[i] và điểm nhỏ nhất
     max_trade_i = a[i] - min_trade
     if max_trade_i > max_trade
         max_trade = max_trade_i

3. Code

Dựa vào giải pháp từ Pesudo code, ta có thể hiện thực với Java để giải quyết bài toán Max Different Stock như sau:

package com.src;

public class Main {
    public static void main(String[] args) {
        int[] a = new int[]{8, 14, 2, 5, 7, 3, 9, 5};
        findMaximumTrade(a);
    }

    public static int findMaximumTrade(int[] a) {
        int minSoFar = 999;
        int maxTrade = 0;
        for (int i = 0; i < a.length; i++) {
            minSoFar = min(a[i], minSoFar);
            int max_i = a[i] - minSoFar;
            if (max_i > maxTrade)
                maxTrade = max_i;
        }
        return maxTrade;
    }

    private static int min(int a, int b) {
        if (a < b)
            return a;
        else
            return b;
    }
}

Về min, max có thể dùng Math.min Math.max của Java cũng ok. Giải pháp này có Time Complexity: O(n) và Space Complexity: O(1).

4. Tham khảo

• Solve Reverse Array with the best solution
• Maximum difference between two elements such that larger element appears after the smaller number

My pleasure when you’re here to read – Have a nice week – Happy Coding!