Trong bài toán này, chúng ta cho một mảng và một số nguyên k. Nhiệm vụ của chúng ta là tạo một chương trình tìm tổng mảng con tối đa bằng cách lật các dấu hiệu của nhiều nhất k phần tử mảng trong C ++.
Mô tả mã - Ở đây, chúng ta sẽ phải tìm nhiều nhất k phần tử để lật trong mảng, điều này sẽ làm cho tổng của mảng con được tạo từ mảng này là tối đa.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào - mảng ={1, -2, 7, 0} k =2
Đầu ra - 10
Giải thích - chúng ta sẽ chỉ lật một phần tử là -2, nó làm cho tổng mảng là 10 là lớn nhất có thể.
Để giải quyết vấn đề này, chúng tôi sẽ sử dụng phương pháp lập trình động để tìm tổng số tối đa có thể có của mảng từ thứ i lập chỉ mục cho thứ j lập chỉ mục và lưu trữ nó trong một mảng maxSumij [i] [j] và xem xét cả hai trường hợp nếu phần tử được lật hoặc không có phần tử lật, điều này sẽ trả về trường hợp tốt nhất, điều này sẽ được thực hiện bằng cách gọi đệ quy đến hàm. Cuối cùng, chúng ta sẽ tìm phần tử lớn nhất từ ma trận maxSumij [i] [j].
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
Maximum subarry sum by fipping signs of at most 2 element is 66