Maximum Array Sum After Switching Consecutive Elements

Tech
Algorithm, Interview

Question

Recently, I’ve heard an algorithm question from a colleague:

Given two arrays $a$ and $b$ with same length $n$, find index $i$ and $j$ $(i < j)$ that, after replacing $a[i],a[i+1],…,a[j-1]$ with $b[i],b[i+1],…,b[j-1]$, the sum of $a$ is maximum.

My first instinct: this is so dynamic programming. However, let’s try brute force first.

Brute Force

For every pair of $(i,j)$, calculating the sum of replaced $a$ costs $o(n)$. And there are $o(n^2)$ pairs of $(i,j)$, so the total time complexity for Brute-force method is $o(n^3)$ with space $o(1)$. I am not going to write down the code. ^_*

Well, if we can use some extra space, we can save sometime to calculate the sum. Here comes the second solution:

Dynamic Programming for Sum

Let’s denote $A_0=B_0=0,\;A_i=\displaystyle\sum_{j=0}^{i-1} a[j], \;B_i=\displaystyle\sum_{j=0}^{i-1} b[j]$ and $S_{ij}$ is the sum after switching elements between index $i$ and $j$.

It is easy to see that $S_{ij}=A_n-A_j+B_j-B_i+A_i$, so if we store all $A_i$ and $B_i$ that calculating the $S_{ij}$ just needs $o(1)$ time. Of course, calculating all $A_i$ and $B_i$ needs $o(n)$ time, but it only needs to be calcaluted once.

So here is C# code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static class MaximumSumCalculator
{
    public static int MaximumSumAfterSwitchingElements(int[] a, int[] b)
    {
        int[] aa = new int[a.Length + 1];
        int[] bb = new int[a.Length + 1];
        aa[0] = 0;
        bb[0] = 0;

        for(int i = 0; i < a.Length; ++i)
        {
            aa[i+1] = aa[i] + a[i];
            bb[i+1] = bb[i] + b[i];
        }

        int maxSum = aa[a.Length];
        for(int j = 1; j <= a.Length; ++j)
        {
            for(int i = 0; i < j; ++i)
            {
                maxSum = Math.Max(maxSum, aa[a.Length] - aa[j] + bb[j] - bb[i] + aa[i]);
            }
        }

        return maxSum;
    }
}

Now by storing the sums, time cost reduces to $o(n^2+n)=o(n^2)$.

Can we further reduce the time cost? Of course we can! Let’s reorganize $S_{ij}$:

So if we construct a new array $C$, what we want is find $i$ and $j$ to make $C[j]-C[i]$ maximum with only one constraint: $i<j$. Does it ring a bell now? Hmm, if it doesn’t, what if $C[i]$ is the stock price on $i$th day, you need to make the max profit out of it with at most one buy and sell? Yes, it is LeetCode No. 121: Best Time to Buy and Sell Stock. Here comes the third solution:

“Best Time to Buy and Sell Stock”

If we sell stock at $i$th day, the max profit we can make is $Profit[i]=Stock[i]-S_{min}[i]$, $S_{min}[i]$ is the least price in the first $i$ days. What we need is $max(Profit[i])$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static class MaximumSumCalculator
{
    public static int MaximumSumAfterSwitchingElements(int[] a, int[] b)
    {
        int sum = a[0];
        int maxProfit = 0;
        int stockPrice = b[0] - a[0];
        int minPrice = stockPrice;

        for(int i = 1; i < a.Length; ++i)
        {
            stockPrice += (b[i] - a[i]);
            minPrice = Math.Min(stockPrice, minPrice);
            maxProfit = Math.Max(maxProfit, stockPrice - minPrice);
            sum += a[i];
        }

        return sum + maxProfit;
    }
}

Now we only need $o(n)$ time to make the max profit out of it!

I guess my colleague cannot ask interviewee of this question any more.

PS

It took me some time to make the math equation display right. Thanks to 然而，然而 and his post 如何在Hexo中渲染公式.