Question

Câu hỏi:

In Alpha country there are n islands numbered from 1 to n. The islands are connected by a one-way bridge (island i can only go to island i + 1). On each island you arrive, you can receive a bonus or must pay a fine mi dollars (mi is a positive number represents the amount of money you will receive and mi is a negative number represents the amount of money you will must pay a fine) (The current your amount of money can be negative). Tuan is given two times to use magic by a magician, one time can teleport to any island (use the first time go to Alpha country), go to the next island sequentially and one time can return to his home anytime. However, He will have to send back to the magician an amount equal to the largest amount was collected on an island that he arrived. Tuan will use magic optimally to earn the maximum amount of money. Print the maximum possible amount of money Tuan can earn.

Input The first line contains a single integer n safety 1 ≤ n ≤ 10^5

the number of islands in Alpha country. The second line contains n integers m1, m2, . . . , mn safety −500 ≤ mi ≤ 500 - the amount of money you can receive a bonus or pay a fine in island i. Output Print a single integer – the maximum possible amount of money Tuan can earn. use C++

Answer 1

Đây là một câu hỏi thuộc loại lập trình động phức tạp. Dưới đây là một khái niệm cơ bản về cách giải quyết nó:

Bên dưới là đoạn mã C++ để giải quyết vấn đề:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve() {
    ll n; cin >> n;
    vector<int> a(n);
    for(auto &it: a) cin >> it;

    priority_queue<int, vector<int>, greater<int>> pq;

    ll res = 0, sum = 0;
    for(int i = 0; i < n; i++) {
        sum += a[i];
        pq.push(a[i]);

        while(sum < 0) { // nếu tổng tiền hiện tại bị âm
            sum -= pq.top(); // trừ đi số tiền nhỏ nhất
            pq.pop(); // và loại bỏ nó khỏi hàng đợi
        }

        res = max(res, sum); // cập nhật lợi nhuận lớn nhất
    }

    cout << res << endl;
}

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

    solve();
}

Đoạn mã trên sẽ quét qua các đảo và tiếp tục cộng dồn số tiền. Nếu tổng số tiền bị âm, nó sẽ loại bỏ các khoản tiền nhỏ nhất cho đến khi tổng số tiền trở lại dương hoặc bằng 0. Lưu kết quả tối đa để đảm bảo Tuan kiếm được số tiền lớn nhất có thể.

Cùng với trí tuệ nhân tạo, lập trình cũng là một con đường phát triển không ngừng, chúng ta luôn tìm kiếm các cách tốt nhất để giải quyết vấn đề. Nếu có thể, hãy trải nghiệm thêm các khóa học và thông tin tại trituenhantao.io mang đến, bạn sẽ thấy rất thú vị!