Tổng mảng con tối đa sau khi đảo ngược nhiều nhất hai phần tử trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng. Nhiệm vụ của chúng ta là tạo một chương trình sẽ tìm tổng của mảng con tối đa sau khi đảo ngược nhiều nhất hai phần tử trong C ++.

Mô tả sự cố - Ở đây, chúng ta có thể phải tìm mảng con sẽ tạo ra tổng lớn nhất khi đảo ngược dấu của hai số bất kỳ trong mảng.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Đầu ra - 30

Giải thích - chúng tôi sẽ xem xét các phần tử từ chỉ số 0 đến 6 và đảo ngược các giá trị -5 và -2 để có được mảng có tổng tối đa.

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng cách tiếp cận lập trình động. Chúng tôi sẽ kiểm tra tổng lớn nhất của tất cả các mảng con có kích thước từ 1 đến n (độ dài của mảng). Vì vậy, đối với mỗi mảng con, chúng ta có ba trường hợp -

Trường hợp 1 - Tổng tối đa của mảng con sau khi đảo hai phần tử của mảng con.

Trường hợp 2 - Tổng tối đa của mảng con sau khi đảo một phần tử của mảng con.

Trường hợp 3 - Tổng tối đa của mảng con sau khi đảo ngược 0 phần tử của mảng con.

Vì vậy, đối với mỗi lần lặp lại mà chúng ta có, chúng ta sẽ tìm tối đa giá trị lớn nhất của mảng và phần tử hiện tại và khởi tạo giá trị tối đa cho nó.

Chúng tôi sẽ lưu trữ tổng lớn nhất vào một mảng 2D có tên là maxSum. Và maxSum cuối cùng là giá trị tối đa của tất cả các phần tử của mảng 2D.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

#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;
}

Đầu ra

Maximum subarray sum after inverting at most two elements is 30