Explaining the Stock Market

Description

Mark Stockle has taken interest in analyzing the stock market. Recently, he has focused on a particular company’s stock. He observes the price of this stock over a period of N days. Then, he stares at these numbers for a long time and tries to identify the patterns and trends in the price. For example, he might notice that near the beginning of the N days, the price was decreasing, but then it steadily rising later. Or he might notice that generally the price was going up with the occasional daily dip. However, he was unable to come up with any rigorous or general approach for analyzing the stock.

One day, his friend suggested the following strategy: he ought to break up the problem of explaining N days of prices into smaller manageable subproblems. In particular, he would divide up the N days into K sets, and explain each set using a single hypothesis. Note that the days in a set do not have to be contiguous.

In his machine learning class, Mark learned the power of Occam’s Razor, which was that simple hypotheses that explain the data tend to generalize better on future data. It was so important for him to have simple hypotheses that he only allowed two types of hypotheses: that the prices of the stock on the days in a set would not increase or not decrease over time. Of course, there must be at least two days per set, since it does not make sense to explain the stock price of one day by itself. Lastly, the most important method to impose simplicity was to have as few hypotheses as possible, i.e. minimize K.

Input

The first line contains N (1 ≤ N ≤ 30), the number of days for which Mark has collected stock prices. The next N lines contain N integers in the range [0, 100], one on each line. These integers represent the stock prices over N days.

Output

On a single line, output K, the minimum number of hypotheses needed to explain the stock data. If it is impossible to explain the data using K hypotheses as described above, simply output 0.

Sample Input

8
1
6
3
5
4
2
7
0
Sample Output

2

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐