Dynamic Programming - more action

Let's look at some more problems to exercise our brains during Christmas time.

Problem III

You are given an N element array filled with integers. Find the non-empty interval in this array with maximal possible sum.

Example:

T = [1, -2, 3, 1, -3, 2, 2, -7, 4, -2, 1]

Here the best solution is interval [2, 6] (indexing from 0) with sum equal to 3 + 1 + (-3) + 2 + 2 = 5.

This is a much different problem than the one from the last post. It was purely combinatorial and this … well, it isn’t.

How would look the naïve solution in this case? – Answering this should be the first thing to do when solving DP problems. It usually helps.

Let’s think … we have to find some interval with the desired property. Why not to check all of the intervals, then? There are n * (n+1) / 2 intervals and each of them can be processed in linear time. So, overall complexity would be around O(n^3).

int maximalSumN3(int T[], int N)
{
 int best, left = -1, right = -1;
 for(int a = 0; a < N; ++a)
  for(int b = a; b < N; ++b)
  {
   int actSum = 0;
   for(int k = a; k <= b; ++k)
    actSum += T[k];
   if(left == -1 || actSum > best)
    best = actSum, left = a, right = b;
  }
 return best;
}

It’s polynomial, which is good, but let’s try to optimize it. Since we can’t change the number of intervals we should probably start with improving the calculation part. We can observe that we perform very often similar calculations. For example counting sum for interval [a, b] is almost the same as [a, b+1]. They differ only by element T[b+1]. Going even further: starting from interval [a, a] following intervals will be processed in constant time:

[a, a+1] : sum(a, a+1) = sum(a, a) + T[a+1]

…

[a, n-1] : sum(a, n-1) = sum(a, n-2) +T

Doing the same for all possible values of a we are getting O(n^2) time complexity.

int maximalSumN2(int T[], int N)
{
 int best, left = -1, right = -1;
 for(int a = 0; a < N; ++a)
 {
  int actSum = 0;
  for(int b = a; b < N; ++b)
  {
   actSum += T[b];
   if(left == -1 || actSum > best)
    best = actSum, left = a, right = b;
  }
 }
 return best;
}

But that is still not enough!

How can it be optimized even more?

Since the current time complexity is comparable with the number of intervals we will have to process more than one interval at the same time in order to achieve better solution. In the last improvement we were looking at how calculations relate to each other for consecutive values of b. We are going to use similar trick this time too.

How do the intervals look like for consecutive values of a?

Let’s see:

[a, n-1], [a, n-2], …, [a, a+1], [a, a]

[a+1,n-1], [a+1, n-2], …, [a+1, a+1]

Except for the [a,a], all of the intervals starting from a have corresponding interval starting from a+1 and their sums differ only by T[a] ( sum(a, b) – sum(a+1, b) = T[a] ). The usual question: how can we use it?

Since almost all of the intervals starting at a behaves like that, it means that probably the best interval starting at a has the same property. There are two cases:

- [a, a] is the best

- [a, b] is the best for some b > a, but sum(a, b) = T[a] + sum(a+1, b) and it is maximal possible. T[a] is constant for given a, so sum(a+1, b) must be the maximal sum starting at a+1 (if it weren’t - sum(a+1, b) < sum(a+1, c), then T[a] + sum(a+1,b ) < T[a] + sum(a+1, c) which means that sum(a, b) < sum(a, c) and sum(a, b) was chosen to be maximal starting at a)

Maybe it could be described better… Basically it means that since almost all of the sums differ by T[a] then maximal sums will too (except for one case). This observation will allow us to implement even better solution, because the best interval starting from each position is more than enough to solve this problem! Let’s see it in code:

// when we want to calculate just the maximal sum
int maximalSumN(int T[], int N)
{
 int best = T[N-1], lastBest = 0;
 for(int a = N-1; a >= 0; --a)
 {
  // the best interval starting at a is either T[a] or T[a] + the best interval starting at a+1
  lastBest = max(lastBest + T[a], T[a]);
  best = max(best, lastBest);
 }
 return best;
}

// when we also want to find the best interval
int maximalSumN(int T[], int N) // N > 0
{
 int best = T[N-1], left = N-1, right = N-1;
 int lastBest = T[n-1], lastRight = N-1;
 for(int a = N-2; a >= 0; --a)
 {
  if(lastBest + T[a] > T[a])
   lastBest = lastBest + T[a];
  else
   lastBest = T[a], lastRight = a;

  if(best < lastBest)
   best = lastBest, left = a, right = lastRight;
 }
 return best;
}

What we found out here is that we can calculate the best intervals starting at each position as fast as (or even faster than) trying to find just the best one. I know that this can be probably hard to discover at the beginning, but it’s just one of the common patterns when solving DP problems. Sometimes solving a bit more that you are being asked for makes thinks much easier. It comes with some experience.

To sum up, we solved it in linear complexity and the solutions is even simpler than the brute force one. Clearly, it can’t be solved faster because we have to at least see what’s in the array which takes linear time.

This was one of the most classical problems in dynamic programming (and not to scare you out one of the simplest). I tried to explain it with many details, because now I want to post much harder problem (at least it looked like it when I told it to some of my friends):

Problem IV

You are given an N element array filled with integers and K small distinct integers. Find the smallest interval in this array that contains all of the K integers.

Example:
Array: {1, 7, 20, 3, 5, 11, 1, 3, 7, 8, 9, 5}
K: 3 - {1, 3, 5}
Smallest interval that contains 1, 3 and 5 is shown in bold above.

Solved already?

Brute force solution looks more or less the same as in the previous problem:

int allKIntegersN3(int T[], int N, int P[], int K)
{
 // each element of array P is smaller than maxSmallInteger
 bool used[maxSmallInteger];
 bool inP[maxSmallInteger];
 for(int i = 0; i < maxSmallInteger; ++i) used[i] = inP[i] = 0;
 for(int i = 0; i < K; ++i) inP[P[i]] = 1;

 int best = N + 1, left, right;
 for(int a = 0; a < N; ++a)
  for(int b = a; b < N; ++b)
  {
   for(int s = 0; s < K; ++s) used[P[s]] = 0;
   int howManyUsed = 0;
   for(int s = a; s <= b; ++s)
   {
    if(inP[T[s]] && used[T[s]] == 0)
     ++howManyUsed, ++used[T[s]];
   }
   if(howManyUsed == K && b - a + 1 < best)
    best = b - a + 1, left = a, right = b;
  }
 return best;
}

It can be also similarly improved to O(N^2) solution ( O(N*(N + K)) to be precise, but let’s assume for simplicity, that K is constant )

int allKIntegersN2(int T[], int N, int P[], int K)
{
 bool used[maxSmallInteger];
 bool inP[maxSmallInteger];
 for(int i = 0; i < maxSmallInteger; ++i) used[i] = inP[i] = 0;
 for(int i = 0; i < K; ++i) inP[P[i]] = 1;

 int best = N + 1, left, right;
 for(int a = 0; a < N; ++a)
 {
  for(int s = 0; s < K; ++s) used[P[s]] = 0;

  int howManyUsed = 0, s = a - 1;
  while(s < N - 1 && howManyUsed < K)
  {
   ++s;
   if(inP[T[s]] && used[T[s]] == 0)
    ++howManyUsed, ++used[T[s]];
  }
  if(howManyUsed == K && s - a + 1 < best)
   best = s - a + 1, left = a, right = s;
 }
 return best;
}

So now we are just looking for the smallest interval starting at given position containing all of the given numbers. Can it be solved even faster? Of course – let’s apply the third optimization. What happens for consecutive values of a?

Let’s assume we have the best solution starting at a ([a, b]) and at a+1 ([a+1, c]) and think how they relate to each other¬. Of course, b <= c; otherwise since [a+1, c] contains all of the necessary numbers then [a, c] as well. Well, [a+1, c] contains all of the numbers that are in [a, b] except for T[a]. But that is easy to control!

Assuming we have the best interval starting at a ([a, b]) to find the best for a+1 we just have to remove T[a] from the solution, check if it changes anything (T[a] could be one of the given integers) and if so, we just have to first position to the right from b that contains T[a]. In code it can look like this:

int allKIntegersN(int T[], int N, int P[], int K)
{
 bool used[maxSmallInteger];
 bool inP[maxSmallInteger];
 for(int i = 0; i < maxSmallInteger; ++i) used[i] = inP[i] = 0;
 for(int i = 0; i < K; ++i) inP[P[i]] = 1;

 int best = N + 1, left, right;
 int howManyUsed = 0, s = -1;
 for(int a = 0; a < N; ++a)
 {
  while(s < N - 1 && howManyUsed < K)
  {
   ++s;
   if(inP[T[s]] && used[T[s]] == 0)
    ++howManyUsed, ++used[T[s]];
  }
  if(howManyUsed == K && s - a + 1 < best)
   best = s - a + 1, left = a, right = s;

  // updating values for a + 1
  if(inP[T[s]] && used[T[s]] == 1)
   --howManyUsed;
  --used[T[s]];
 }
}

I hope this is quite clear. I can write some more about it if necessary. Anyway, we solved the latter problem also in O(N)! What is interesting, we did it in almost the same way as the previous one.

To cheer you up (hopefully not to frighten you) I can say that this problem was used in the job interview for some big company. It wasn’t that hard after all, was it? We just needed to know in detail about how can be solved the classical problem.

Merry Christmas!