#### Discover more from Daily bit(e) of C++

# 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.