LeetCode53 暴破、分治和dp

题目描述

一：暴力破解

  最直接的做法，按着思路直接写代码就好了。

二：分治法

  刚开始自己试写了很久，都失败了，后来看了紫书和题解写出来了。

  首先用二分法不断递归将数组缩小，变为最小的子结构：

假设两个子结构A和B，我们得出了他们两个当中的最大值，我们还得看看他们两个加起来会不会比个各自大，由于要求时连续的，所以我们要从他们的中间开始向两边求解，然后将左右两边的解加起来，便是他们合起来的最优解。

三：动态规划

   用dp得从右往左累加，因为题目要求必须时连续的数字，从右往左累加才能保证得出来的解数字是连续的。

dp过程