2
$\begingroup$

I recently came across the sentence in the Book Introduction to Algorithms section 4.1 The maximum sub-array problem:

We still need to check $\binom{n-1}{2} = \Theta(n^2)$ subarrays for a period of $n$ days.

Here $n$ is the number of days taken as an example to show the changes in price of stock.

We can consider this is the size of an array A.

Where we are provided with an Array A and we need to find the net change is maximum from the first day to the last day.

To explain more specifically it means for an array $A$ of size $n$ we need to check $\binom{n-1}{2}$ subarrays.

But, I cannot understand how we need $\binom{n-1}{2}$ sub-arrays?

If we take an array of size 5 could someone please explain to me why we need only 6 sub-arrays. Won't the sub-arrays be:

[1...5]
[1...4]
[1...3]
[1...2]

[2...4]
[2...5]


[3...5]
[4...5]

Please correct me if I am wrong. References: Maximum Subarray Problem

The Maximum Sub-array problem Thank you.

$\endgroup$
6
  • $\begingroup$ What is the maximum sub-array problem? Please make your question self-contained. I don't understand the current description (we are provided with an Array A and we need to find the net change is maximum from the first day to the last day). $\endgroup$ – Yuval Filmus Jun 20 '20 at 13:46
  • $\begingroup$ Please have a look. $\endgroup$ – Sachin Bahukhandi Jun 20 '20 at 14:08
  • 1
    $\begingroup$ You are missing [2...3] and [3...4]. Together, you get $10 = \binom{n}{2}$. I'm not sure where $\binom{n-1}{2}$ comes from – could be a mistake, or could only be understood if you bothered to define your problem formally. $\endgroup$ – Yuval Filmus Jun 20 '20 at 14:10
  • $\begingroup$ I added the screenshot of the section I am facing problem at. Please have a look. $\endgroup$ – Sachin Bahukhandi Jun 20 '20 at 14:23
  • $\begingroup$ I suggest considering very small $n$, say $n=1$ and $n=2$, and seeing what happens. It might be that a parameter $n$ correspond to an array of size $n-1$, for example. $\endgroup$ – Yuval Filmus Jun 20 '20 at 15:43
2
$\begingroup$

You have found a bug in one of the most famous textbooks on computer science!


While there are $n$ days, there are only $n-1$ changes in price of stock. So there are $\binom{n-1}{2}$ subarrays of the array of the changes in price of stock, assuming that a subarray starts and ends at different indices.

That explain away, I believe, why the books says "we still need to check $\binom{n-1}{2} = \Theta(n^2)$ subarrays for a period of $n$ days".


However, in fact, you are right that we still need to check $\binom n2$ subarrays.

Let $B$ be the array of the daily prices for a period of $n$, starting at index (day) 0. Let $A$, as in the book, be the corresponding array of the price changes, starting at index (day) 1. If you select to buy on day $i$ and sell on day $j$, making a profit of $B[j]-B[i]$, it corresponds to subarray $A[i+1\,..\,j]$, i.e., $(A[i+1], A[i+2], \cdots, A[j])$. Please note the change of indices from $i$ and $j$ in $B$ to indices $i+1$ and $j$ in $A$. While $i$ and $j$ must be different always as "you are allowed to buy one unit of stock only one time and then sell it at a later date", $i+1$ and $j$ are the same when $j=i+1$, i.e., when you sell the next day.

Let us verify the sum of selected numbers in $A$ is indeed $B[j]-B[i]$. $$\begin{aligned} &\quad A[i+1]+A[i+2]+\cdot+A[j]\\ &=(B[i+1]-B[j])+(B[i+2]-B[i+1])+\cdot+(B[j]-B[j-1])\\ &=B[j]-B[i].\end{aligned}$$ Note the formula does hold when $j=i+1$.

Besides the subarrays of $A$ that start and end at different indices, we must consider the subarrays with the same starting index and ending index. There are $n-1$ of them, i.e., the subarray whose only element is $A[1]$, the subarray whose only element is $A[2]$, ... and the subarray whose only element is $A[n-1]$. Since $\binom{n-1}2+(n-1)=\binom n2$, we still need to check $\binom n2$ subarrays.

For example, if the daily prices for a period of $3$ days are $B=(85, 105, 102)$, the changes of prices are $A=(20, -3)$. If we do not check the subarray of $A$, $(20)$, which stands for buying at price $85$ on day $0$ and selling at price $105$ on day $1$, we will miss the optimal profit, $20$.


This simple and obvious bug is not listed on the errata page for Introduction to Algorithms, Third Edition. It is incredible that this bug has been living comfortably in that popular book for over ten years before you pointed out explicitly.

On the other hand, many people might have been aware of that bug, although I did not notice it. The focus of that mistaken statement is "we still need to check $\Theta(n^2)$ subarrays for a period of $n$ days". The actual number of subarrays that should be checked is not that critical, as long as its level of asymptotic growth is correct. While misleading otherwise, that bug does not harm much the development of a better algorithm.

$\endgroup$
10
  • $\begingroup$ Am I the only one to notice this Or is this really a defect someone else pointed out before. I could never find any relevant questions related to this. $\endgroup$ – Sachin Bahukhandi Jun 20 '20 at 19:27
  • 1
    $\begingroup$ Be careful. The books reads at one point, "just try every possible pair of buy and sell dates in which the buy date precedes the sell date. A period of $n$ days has $\binom n2$ such pairs of dates." Buying on day $0$ has been considered, of course, in the array figure 4.3. Otherwise, what is the meaning of the very first entry, 13, which stands for the difference of day 0 and day 1, if you cannot buy on the day 0? I would encourage you, to follow your own example, to read carefully. $\endgroup$ – John L. Jun 20 '20 at 19:47
  • 1
    $\begingroup$ One of the reason why this bug, which is obvious once pointed out, has been overlooked by people is that the point of that statement is "we still need to check $\Theta(n^2)$ subarrays for a period of $n$ days". The actual formula for the number of checks is not the focus. $\endgroup$ – John L. Jun 20 '20 at 21:13
  • 1
    $\begingroup$ Please read the whole section carefully, following your own example. Also see my updated answer. $\endgroup$ – John L. Jun 21 '20 at 19:05
  • 1
    $\begingroup$ Sorry I got it by re- reading. Thank you so much. $\endgroup$ – Sachin Bahukhandi Jun 22 '20 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.