Tổng dãy con lớn nhất bằng cách đổi dấu tối đa K phần tử trong C++

Trong bài toán này, chúng ta được cho một mảng và một số nguyên k. 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 bằng cách đổi dấu của tối đa k phần tử trong mảng.

Mô tả thuật toán – Ta phải tìm tối đa k phần tử để đổi dấu trong mảng sao cho tổng dãy con tạo ra từ mảng này là lớn nhất.

Ví dụ:

Đầu vào – mảng = {1, -2, 7, 0}, k = 2

Đầu ra – 10

Giải thích – Chỉ cần đổi dấu phần tử -2, mảng trở thành {1, 2, 7, 0} với tổng là 10 – giá trị lớn nhất có thể.

Để giải quyết, ta sử dụng quy hoạch động (dynamic programming) để tìm tổng lớn nhất có thể của dãy con từ chỉ số i đến j và lưu vào ma trận maxSumij[i][j], xem xét cả hai trường hợp: phần tử được đổi dấu hoặc không. Việc này được thực hiện bằng gọi hàm đệ quy. Cuối cùng, ta tìm phần tử lớn nhất trong ma trận maxSumij.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;
#define right 2
#define left 4
int arraySumij[left][right];

int findSubarraySum(int i, int flips, int n, int a[], int k) {
    if (flips > k)
        return -1e9;
    if (i == n)
        return 0;
    if (arraySumij[i][flips] != -1)
        return arraySumij[i][flips];
    int maxSum = 0;
    maxSum = max(0, a[i] + findSubarraySum(i + 1, flips, n, a, k));
    maxSum = max(maxSum, -a[i] + findSubarraySum(i + 1, flips + 1, n, a, k));
    arraySumij[i][flips] = maxSum;
    return maxSum;
}

int maxSubarraySumFlip(int a[], int n, int k) {
    memset(arraySumij, -1, sizeof(arraySumij));
    int maxSum = -100;
    for (int i = 0; i < n; i++)
        maxSum = max(maxSum, findSubarraySum(i, 0, n, a, k));
    return maxSum;
}

int main() {
    int a[] = {-3, 56, -1, 8};
    int n = sizeof(a) / sizeof(a[0]);
    int k = 2;
    cout << "Maximum subarry sum by fipping signs of at most " << k << " element is " << maxSubarraySumFlip(a, n, k);
    return 0;
}

Kết quả

Maximum subarry sum by fipping signs of at most 2 element is 66