Finding the Maximum Inversion Sum of an Array

Question

You are given a 0-indexed array vect of n integers. You need to perform the following 2 operations exactly once-

• Choose an index i {0, 1, 2, ..., n-1} and multiply the entire prefix segment {0..i} by -1.
  
• Choose an index j {0, 1, 2, ..., n-1} and multiply the entire suffix segment {j...n-1} by -1.
  

Choosing i and j, we need to maximize the entire sum of all elements of the array.

Note:
It is possible for the prefix and suffix segments to overlap, i.e. when i = j or i > j. As expected, when a sub-segment undergoes both operations, it's value remains unchanged.

Approach:

• Make the array 1-based and calculate the prefix pref and suffix suff sums.
• While calculating the maximum sum at any index i and j where i < j, we have
  sum = (-1)*pref[i] + Z + (-1)*suff[j]
  Z can be calculated as pref[j-1] - pref[(i+1)-1]. Z = {} when j - i = 1.
• We can only have j > i as overlapping sub-segments would remain the same and have no effect on the final answer.
• Iterate for different values of i and j.

Time Complexity - O(n^2)

Observations

• If none of the elements in pref is negative, we can only negate pref[1] to reduce the maximum sum as little as possible. Similarly, for suff we can do suff[n].
• If atleast one of the elements in both pref and suff is negative, lets say pref[i] < 0 and suff[j] < 0, our maximum answer will always involve negating pref[i] or suff[j] or both if i < j.

We can do slight optimizations using the above observations, but it would not change the Time Complexity (a case where all elements in vect are negative, leading to pref and suff have all negative elements).

Code (in C++)

using ll = long long;

ll getMaxInvSum(vector<int> vect) {
    int n = vect.size();
    
    vector<ll> pref(n+2), suff(n+2); // add dummy element at the front and back of vect
    
    pref[0] = 0;
    for(int i=0; i<n; i++) pref[i+1] = pref[i] + vect[i];
    pref[n+1] = pref[n]; 
    
    suff[n+1] = 0;
    for(int j=n-1; j>=0; j--) suff[j+1] = suff[j+2] + vect[j];
    suff[0] = suff[1];
    
    ll ans = pref[n]; // pref[n+1], suff[0], suff[1]
    
    for(int i=1; i<n; i++) {
        for(int j=i+1; j<=n; j++) {
            if(j-i == 1) 
                ans = max(ans, pref[i]*(-1) + suff[j]*(-1));
            else
                ans = max(ans, pref[i]*(-1) + suff[j]*(-1) + pref[j-1] - pref[i+1-1]);
        }
    }
    
    return ans;
}

How can I improve on the Time Complexity ?

Answer 1

Let me show the algorithmic solution (O(n) time complexity), while skipping its implementation.

First of all, we can state the problem in a different way: we don't let overlapping, e.g.

    a, b, c, d, e, f, g
    |           |

          |           |

which equals to

    a, b, c, d, e, f, g
    |  |

                   |  |

but we allow empty prefixes and suffixes instead:

    # f .. g suffix, empty prefix
    a, b, c, d, e, f, g
    |           |
    |                 |

    # a .. b prefix, empty suffix
    a, b, c, d, e, f, g
    |                 |
          |           |

    # empty prefix and suffix
    a, b, c, d, e, f, g
    |                 |
    |                 |

So we can solve the problem in linear time: find the best prefix by using rolling sums (best prefix must have negative minimum sum):

items:
    1, 2, 3, -9, -8, 3, 4, -1
sums:
    1  3  6  -3 -11 -8 -4  -5
                  ^
                  best prefix (the sum is minimal and negative)

similar we can compute the suffix (we compute sums staring from the end in this case):

items:
    1, 2, 3, -9, -8, 3, 4, -1
sums:
   -5 -6 -8 -11  -2  6  3  -1
              ^
              best suffix

If best prefix and best suffix don't overlap, return them as an answer. If prefix and suffix overlap, we should choose between two options:

1. Take the best prefix and the best suffix which doesn't overlap the taken prefix
2. Take the best suffix and the best prefix which doesn't overlap the taken suffix

In the example above:

1. Choosing 1, 2, 3, -9, -8 prefix and -1 suffix, we have 19
2. Choosing empty prefix and -9 -8 3 4 -1 suffix, we have 17

So far so good, we choose 1st option (19) which is

   1, 2, 3, -9, -8, 3, 4, -1
   |             |        ||

Answer 2

This can be done using dp.

Let-

• dpp[i][0] - value obtained by flipping all elements from 0 to i.
• dpp[i][1] - maximum value obtained until index i by not flipping i.

dpp[i][0] = dpp[i-1][0] + (-1)*arr[i]
dpp[i][1] = max(dpp[i-1][0], dpp[i-1][1]) + arr[i]

We can compute for indexes from 1 to n-2.
sum = max(dp[i][0], dp[i][1]) + (-1)*suff[i+1]

We can similarly create a dp for suffix and the check for a maximum answer.

int getMaxInvSum(vector<int>& arr) {
    int n = arr.size();   
    vector<int> pref(n), suff(n);
 
    pref[0] = arr[0];
    for(int i=1; i<n; i++) pref[i] = arr[i] + pref[i-1];
    suff[n-1] = arr[n-1];
    for(int i=n-2; i>=0; i--) suff[i] = arr[i] + suff[i+1];
 
    int ans = pref[n-1] & suff[0];
 
    vector<vector<int>> dpp(n, vector<int>(2));
    dpp[0][0] = (-1)*arr[0];
    dpp[0][1] = (-1)*arr[0];
    for(int i=1; i<n-1; i++) {
        dpp[i][0] = (-1)*arr[i] + dpp[i-1][0];
        dpp[i][1] = arr[i] + max(dpp[i-1][0], dpp[i-1][1]);
    }
 
    for(int i=0; i<n-1; i++)
        ans = max(ans, max(dpp[i][0], dpp[i][1]) + (-1)*suff[i+1]);
 
    vector<vector<int>> dps(n, vector<int>(2));
    dps[n-1][0] = (-1)*arr[n-1];
    dps[n-1][1] = (-1)*arr[n-1];
    for(int i=n-2; i>0; i--) {
        dps[i][0] = (-1)*arr[i] + dps[i+1][0];
        dps[i][1] = arr[i] + max(dps[i+1][0], dps[i+1][1]);
    }
 
    for(int i=n-1; i>0; i--)
        ans = max(ans, max(dps[i][0], dps[i][1]) + (-1)*pref[i-1]);
 
    return ans;
}