Leetcode刷题5—最大子序和
2024-09-04 22:56:09
一、题目要求
二、题目背景
动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，具有天然剪枝的功能，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
链接：https://leetcode-cn.com/tag/dynamic-programming/
来源：力扣（LeetCode）
三、解法
（1）看到这个题目首先想到的是一层一层计算，第一层找到最大的值对应的索引；第二层找两两数组之和的最大索引，如果都小于0则退出循环；第三层找连续三个数组之和，如果都小于0等退出循环，依次类推
（2）采用动态规划的方法
初始化sum=0，ans=num[0]，不断向右累加，如果sum大于等于0，则记录，否则sum置为num[i]
最新文章
- js兼容性
- Oracle 11g 新特性之Highly Available IP（HAIP）
- 用world写blog
- mysql锁
- 操作系统性能分析与优化V1.0
- UnityShader之顶点片段着色器Vertex and Fragment Shader【Shader资料】
- 获取网络状态ios（2G、3G、4G、Wifi）
- (08)odoo继承机制
- POJ 1607
- Booting ARM Linux
- NET Core1
- Net 一个请求的处理流程
- Html5 移动端 触摸滑动事件
- MyBatis关联关系
- FJOI2017 RP++
- 一个蒟蒻对FFT的理解（蒟蒻也能看懂的FFT）
- LeetCode 46 全排列
- KVM源代码框架
- linux rsync同步工具
- 网络流--最大流ek模板