编程介的小学生 2016-12-28 02:53 采纳率: 20.5%
浏览 764
已采纳

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条回答

  • threenewbee 2016-12-31 08:24
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题