Hiếu đầu tư vàng

HIEUVANG - Hiếu đầu tư vàng

Điểm: 1,00

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, JavaScript, Kotlin, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Trong n ngày liên tiếp, Hiếu ghi lại giá vàng 9999 của từng ngày để tự đánh giá các quyết định đầu tư của mình.

Sau khi đã có toàn bộ bảng giá của n ngày đó, Hiếu muốn biết: nếu trong giai đoạn này anh ấy được thực hiện đúng một giao dịch thì lợi nhuận lớn nhất có thể đạt được là bao nhiêu.

Một giao dịch gồm:

chọn một ngày để mua vàng
chọn một ngày sau đó để bán vàng

Lợi nhuận thu được bằng:

~\text{giá bán} - \text{giá mua}~

Hãy tính lợi nhuận lớn nhất mà Hiếu có thể đạt được. Nếu không có cách nào để có lãi, hãy in ra 0.

Input

Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 2 \cdot 10^5)~.
Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^9)~, trong đó ~a_i~ là giá vàng ở ngày thứ ~i~.

Output

In ra một số nguyên duy nhất là lợi nhuận lớn nhất có thể đạt được. Nếu mọi giao dịch đều không có lãi thì in 0.

Ví dụ

Input

6
7 1 5 3 6 4

Output

Giải thích

Mua ở ngày có giá ~1~ và bán ở ngày có giá ~6~, nên lợi nhuận lớn nhất là ~6 - 1 = 5~.

Bình luận

Please read the guidelines before commenting.

Mọi người check hộ em sao lại sai với ạ

include <bits/stdc++.h>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

// your code go here



int n;

int a[n];

cin >> n;

int min = 0;

int max = 0;

for (int i = 0; i < n; i++) {

    cin >> a[i];

}

min = a[0];

max = a[0];

int profit = 0;

for (int i = 1;i < n; i++) {

    int tempProfit = 0;

    if (a[i] > max) {

        max = a[i];

        tempProfit = a[i] - min;

    } else if (a[i] < max) {

        if (a[i] < min) {

            min = a[i];

            max = 0;

        }

    }

    if (tempProfit > profit) profit = tempProfit;

}

cout << profit << endl;

return 0;

}

0

hoc0g đã bình luận lúc 11, Tháng 5, 2026, 13:24

hay

0

bgb đã bình luận lúc 6, Tháng 5, 2026, 8:30

hello mn =)

spoil!

ý tưởng 
Duyệt từ đầu đến cuối, mỗi ngày tính:
Lãi hôm nay = giá hôm nay - giá thấp nhất đã thấy trước đó
Cập nhật đáp án = max(đáp án, lãi hôm nay)
Cập nhật giá thấp nhất = min(giá thấp nhất, giá hôm nay)

code tham khảo (c++)

    #include <bits/stdc++.h>

    using namespace std;

    int main() {
        ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

        int n;
        cin>>n;
        int a[n+1];
        for(int i = 1; i <= n; ++i) cin >> a[i];
        long long mi = a[1], ans = 0;;

        for (int i = 2; i <= n; ++i) {
            ans = max(ans, a[i] - mi);
            mi = min(mi, 1LL * a[i]);
        }

        cout << ans << endl;
    }

def init(self, capacity): self.capacity = capacity self.cache = {} # key -> node self.head = Node() # dummy head self.tail = Node() # dummy tail self.head.next = self.tail self.tail.prev = self.head

def get(self, key):
    if key in self.cache:
        node = self.cache[key]
        self._move_to_front(node)
        return node.value
    return -1

def put(self, key, value):
    if key in self.cache:
        node = self.cache[key]
        node.value = value
        self._move_to_front(node)
    else:
        node = Node(key, value)
        self.cache[key] = node
        self._add_to_front(node)
        if len(self.cache) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

def _move_to_front(self, node):
    self._remove(node)
    self._add_to_front(node)

Độ phức tạp: O(1) cho cả get và put

Cách 2: Ordered Dict (Python) from collections import OrderedDict

class LRUCache: def init(self, capacity): self.capacity = capacity self.cache = OrderedDict()

def get(self, key):
    if key in self.cache:
        self.cache.move_to_end(key)
        return self.cache[key]
    return -1

def put(self, key, value):
    if key in self.cache:
        self.cache.move_to_end(key)
    self.cache[key] = value
    if len(self.cache) > self.capacity:
        self.cache.popitem(last=False)

HIEUVANG - Hiếu đầu tư vàng

Hiếu đầu tư vàng

Input

Output

Ví dụ

Input

Output

Giải thích

Bình luận

include <bits/stdc++.h>

Ủng hộ Luyện Code Online