Daily bit(e) of C++ | Maximum subsequence dot product
Daily bit(e) of C++ #322, Common interview problem: Maximum subsequence dot product.
Today, we will look at a common C++ interview problem: Maximum subsequence dot product.
Given two arrays of integers, determine the maximum dot product of subsequences formed from these arrays.
The subsequences must have the same length and be non-empty but do not have to be formed from consecutive elements.
For example, for the input {3,0,5,-6,1},{2,4,0,3}, the maximum dot product is formed by picking the subsequences {3,5,1} and {2,4,3}, resulting in the total 29.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/zeWaGPv9x.
Solution
Consider the first pair of elements we pick for the dot product, first[i] and second[j]. The dot product then will be first[i]*second[j] plus whatever we can achieve in the remaining suffixes, i.e. first[i]*second[j] + suffix(i+1,j+1).
If we do not pick this pair, then the dot product is: max(suffix(i+1,j),suffix(i,j+1)).
If we treat suffix as a 2D array, we can calculate the maximum by iterating over this array, bottom-up, right-to-left. However, since we only ever require the values for i+1 and j+1 we can further optimize our memory utilization and use two 1D arrays, one corresponding to suffix[i+1] and one corresponding to suffix[i].
There is, however, one last problem. Since we are calculating these values iteratively, we need a baseline value (zero), and because of this, our algorithm allows for empty subsequences. To deal with that, we have to explicitly check whether we are in a situation where one array only contains positive values and the other only negative, forcing us to pick a dot product with a negative total.
