Tổng dãy con liên tiếp lớn nhất trong O(n) bằng tổng tiền tố trong C++

Đề bài

Cho một mảng chứa các số nguyên dương và âm, hãy tìm tổng lớn nhất của một dãy con liên tiếp trong mảng đó.

Ví dụ

Nếu mảng đầu vào là {-12, -5, 4, -1, -7, 1, 8, -3} thì kết quả là 9.

Thuật toán

• Tính tổng tiền tố (prefix sum) của mảng đầu vào.
• Khởi tạo: min_prefix_sum = 0, res = -∞.
• Duyệt vòng lặp từ i = 0 đến n-1 (n là kích thước mảng):
  • cand = prefix_sum[i] - min_prefix_sum.
  • Nếu cand lớn hơn res (tổng dãy con lớn nhất hiện tại), cập nhật res = cand.
  • Nếu prefix_sum[i] nhỏ hơn min_prefix_sum (tổng tiền tố nhỏ nhất cho đến nay), cập nhật min_prefix_sum = prefix_sum[i].
• Trả về res.

Mã nguồn C++

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

int maximumSumSubarray(int *arr, int n) {
    int minPrefixSum = 0;
    int res = numeric_limits<int>::min();
    int prefixSum[n];
    prefixSum[0] = arr[0];
    for (int i = 1; i < n; i++) {
        prefixSum[i] = prefixSum[i - 1] + arr[i];
    }
    for (int i = 0; i < n; i++) {
        res = max(res, prefixSum[i] - minPrefixSum);
        minPrefixSum = min(minPrefixSum, prefixSum[i]);
    }
    return res;
}

int main() {
    int arr[] = {-12, -5, 4, -1, -7, 1, 8, -3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Result = " << maximumSumSubarray(arr, n) << endl;
    return 0;
}

Kết quả

Khi biên dịch và chạy chương trình trên, kết quả đầu ra là:

Result = 9