Cannot understand the relevance of $\binom{n-1}{2}$ subarrays in The Maximum Sub-array Problem

Question

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

Thank you.

Answer 1

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.