Tổng dãy con lớn nhất sau khi đảo ngược tối đa hai phần tử trong C++

Trong bài toán này, chúng ta được cho một mảng. Nhiệm vụ là viết chương trình tìm tổng dãy con liên tiếp lớn nhất sau khi đảo ngược dấu của tối đa hai phần tử trong mảng.

Mô tả bài toán – Ta phải tìm dãy con cho tổng lớn nhất khi đảo dấu của hai số bất kỳ trong mảng.

Ví dụ:

Đầu vào – mảng = {-5, 1, 3, 8, -2, 4, 7}

Đầu ra – 30

Giải thích – Xét dãy con từ chỉ số 0 đến 6, đảo dấu -5 và -2 để có mảng con có tổng lớn nhất.

Để giải quyết, ta dùng quy hoạch động. Ta kiểm tra tổng lớn nhất của tất cả các dãy con có độ dài từ 1 đến n. Với mỗi dãy con, có ba trường hợp:

• Trường hợp 1 – Tổng lớn nhất sau khi đảo dấu hai phần tử.
• Trường hợp 2 – Tổng lớn nhất sau khi đảo dấu một phần tử.
• Trường hợp 3 – Tổng lớn nhất không đảo dấu phần tử nào.

Mỗi lần lặp, ta tìm giá trị lớn nhất giữa tổng hiện tại và phần tử hiện tại, sau đó cập nhật. Tổng lớn nhất được lưu vào mảng 2D maxSum. Kết quả cuối cùng là giá trị lớn nhất trong mảng này.

Mã nguồn C++

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

int findMaxSubarraySum(int a[], int n) {
    int maxSubarraySum = 0;
    int* arr = new int[n + 1];
    for (int i = 1; i <= n; i++)
        arr[i] = a[i - 1];
    int** maxSum = new int*[n + 1];
    for (int i = 0; i <= n; i++)
        maxSum[i] = new int[3];
    for (int i = 1; i <= n; ++i) {
        maxSum[i][0] = max(arr[i], maxSum[i - 1][0] + arr[i]);
        maxSum[i][1] = max(0, maxSum[i - 1][0]) - arr[i];
        if (i >= 2)
            maxSum[i][1] = max(maxSum[i][1], maxSum[i - 1][1] + arr[i]);
        if (i >= 2)
            maxSum[i][2] = maxSum[i - 1][1] - arr[i];
        if (i >= 3)
            maxSum[i][2] = max(maxSum[i][2], maxSum[i - 1][2] + arr[i]);
        maxSubarraySum = max(maxSubarraySum, maxSum[i][0]);
        maxSubarraySum = max(maxSubarraySum, maxSum[i][1]);
        maxSubarraySum = max(maxSubarraySum, maxSum[i][2]);
    }
    return maxSubarraySum;
}

int main() {
    int arr[] = {-5, 1, 3, 8, -2, 4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum subarray sum after inverting at most two elements is " << findMaxSubarraySum(arr, n);
    return 0;
}

Kết quả

Maximum subarray sum after inverting at most two elements is 30