Maximum Subarray Sum after inverting at most two elements in C++

In this problem, we are given an array. Our task is to create a program that will find the maximum subarray sum after inverting at most two elements in C++.

Problem description − Here, we can have to find the subarray that will produce the maximum sum on inverting the sign of any two numbers of the array.

Let’s take an example to understand the problem,

Input − array = {-5, 1, 3, 8, -2, 4, 7}

Output − 30

Explanation − we will consider elements from index 0 to 6 and invert values -5 and -2 to get the array with max sum.

To solve this problem, we will use a dynamic programming approach. We will check for the maximum sum of all subarray of size 1 to n(length of the array). So, for each subarray, we have three cases −

Case1 − Maximum sum of the subarray after inverting two elements of the subarray.

Case2 − Maximum sum of the subarray after inverting one element of the subarray.

Case3 − Maximum sum of the subarray after inverting zero elements of the subarray.

So, for every iteration that we have, we will find maximum of maxsum of the array, and current element and initialise the max to it.

We will store the maximum sum into a 2D array named maxSum. And the final maxSum is a maximum of all the elements of the 2D array.

Example

Program to show the implementation of our solution,

 Live Demo

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

Output

Maximum subarray sum after inverting at most two elements is 30