LeetCode53 暴破、分治和dp

题目描述

一:暴力破解

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

二:分治法

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

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

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

三:动态规划

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

dp过程
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。