分治法的应用——归并排序

既然我们上一篇讲到了分治法，那么就来提一提由分治法为核心的一个排序算法——归并排序

最大连续和问题

今天开始写新的一章了，今天要讲的算法就是很常见的分治法了，分治法，顾名思义就是将问题不断分割成子问题然后逐个击破的一种常用算法。

首先来介绍一下今天的题目，今天的题目意思非常简单，我有n个数，需要你编写程序算出哪一个连续区间的数字加起来最大，只需输出最大值就可以了。例如比如有五个数，1,2,3,4,5，那么最大值就是15；又例如五个数为-4,2,3,4,-1，那么就是9为最大值了。当然，在某些特殊情况下一个数也可以变成一个区间。

今天这道题目是埃及分数的加强版，与其说是加强版，还不如说只是加了几行代码而已，所以并不会比埃及分数难多少。如果不了解埃及分数请在我的博客中查看我以前对埃及分数特别介绍的一篇文章

今天这道题还是关于暴力求解的。

今天这道题目可是花了不少时间才做出来的，一是一开始我完全没看懂题目，一脸懵逼完全；二是经历了无数次的超时，最后发现了原因——有一个剪枝的地方不小心写错了，多循环了好多次，但是答案还是正确的。。。这就非常尴尬了。

比特币发展

• 创世区块使用了一条新闻作为信息记录
• 每一个区块都会有一个固定的编号，创世区块的编号为0，这个编号叫做区块的高度，该区块后续区块的个数为区块的深度
• 初始挖到一个区块奖励50个比特币，每次当比特币挖出来21万的时候奖励就会减半
• 大概每四年就减半

从今天起后面的一系列关于区块链的博客都是我的学习笔记，主要目的是为了自己可以多次重复温习，顺便分享给看我博客的人。里面的一些话与文章并不都是本人所创作，这只是一个摘录本，但是很多都是手打。
前面说了，主要是为了自己看，放博客里只是顺便，所以不喜勿喷。

今天的这道题目是一道比较有意思的题目，里面有一些关于图的概念，话不多说，马上来看题目吧！

上一篇博客中我特意介绍了并查集，那么今天就来特意讲一下并查集的一个具体的应用。