I am dealing with the following problem:
The stock has a known specific price in each day, we want to buy the stock in one day and sell it in another day in a way that we maximize the profit.
The number of days is $n$.
The boring way to solve it is to check all possible pairs of date. For example, buy in day $1$ and sell in day $2$, buy in day $1$ and sell in day $3$, buy in day $1$ and sell in day $6$ ...
I want to count all possible pairs:
My Solution : The first day has $n-1$ pairs because we can buy in the first day and then we can sell in another other day. In the same way we find that day two has $n-2$ pairs, the third day has $n-3$ pairs, the day $n-1$ has $1$ pair, and the last day has $0$ pair
So number of possible pairs is:
$$(n-1) + (n-2) + (n-3)+ ... + 1 + 0$$
Which is a famous Triangular Number, and is equal to: $\dfrac{n(n-1)}{2}$
My Question : The books states that it is $2^n$ as you can see:
What am I missing please?
P.S.
Though I know that this is a Maximum Subarray Problem, I am trying to use the brute-force solution for learning purposes.