最大子序和

$images\cherry_red.png$ 1 Leetcodegaogaotwo

$images\cherry_blue.png$ 1.1 链表

$images\cherry_orange.png$ 1.1.1 分割链表

$images\cherry_orange.png$ 1.1.2 反转链表

$images\cherry_orange.png$ 1.1.3 快慢指针链表的中间节点

$images\cherry_orange.png$ 1.1.4 链表的倒数第k个节点

$images\cherry_orange.png$ 1.1.5 回文链表

$images\cherry_orange.png$ 1.1.6 链表的删除

$images\cherry_orange.png$ 1.1.7 链表反转2

$images\cherry_orange.png$ 1.1.8 链表的第一个相交节点

$images\cherry_blue.png$ 1.2 dfs

$images\cherry_orange.png$ 1.2.1 岛屿数量

$images\cherry_orange.png$ 1.2.2 机器人的运动范围

$images\cherry_orange.png$ 1.2.3 字符串的全排列(回溯算法)

$images\cherry_orange.png$ 1.2.4 判断一个数字是否可以表示成三的幂的和

$images\cherry_orange.png$ 1.2.5 不同路径III dfs+回溯

$images\cherry_orange.png$ 1.2.6 组合总和 dfs+回溯

$images\cherry_orange.png$ 1.2.7 子集 dfs or 状态枚举

$images\cherry_blue.png$ 1.3 bfs

$images\cherry_blue.png$ 1.4 双指针

$images\cherry_orange.png$ 1.4.1 奇数在前，偶数在后

$images\cherry_blue.png$ 1.5 二维矩阵的前缀和

$images\cherry_orange.png$ 1.5.1 1074. 元素和为目标值的子矩阵数量

$images\cherry_orange.png$ 1.5.2 304. 二维区域和检索 - 矩阵不可变

$images\cherry_blue.png$ 1.6 数组变化

$images\cherry_orange.png$ 1.6.1 大数加减法

$images\cherry_orange.png$ 1.6.2 717. 1 比特与 2 比特字符

$images\cherry_blue.png$ 1.7 排序算法

$images\cherry_orange.png$ 1.7.1 把数组排成最小的数

$images\cherry_orange.png$ 1.7.2 根据字符出现的次数频率进行排序

$images\cherry_orange.png$ 1.7.3 最大数

$images\cherry_orange.png$ 1.7.4 969. 煎饼排序

$images\cherry_blue.png$ 1.8 dp动态规划

$images\cherry_orange.png$ 1.8.1 斐波那契数列

$images\cherry_orange.png$ 1.8.2 俄罗斯套娃信封问题

$images\cherry_orange.png$ 1.8.3 分割回文串

$images\cherry_orange.png$ 1.8.4 01背包

$images\cherry_orange.png$ 1.8.5 打家劫舍II

$images\cherry_orange.png$ 1.8.6 青蛙过河

$images\cherry_orange.png$ 1.8.7 最长回文子串

$images\cherry_orange.png$ 1.8.8 目标和（01背包）

$images\cherry_orange.png$ 1.8.9 最大子序和

$images\cherry_blue.png$ 1.9 滑动窗口

$images\cherry_orange.png$ 1.9.1 绝对差不超过限制的最长连续子数组

$images\cherry_orange.png$ 1.9.2 三数之和

$images\cherry_blue.png$ 1.10 二叉树性质

$images\cherry_orange.png$ 1.10.1 二叉树的最小深度

$images\cherry_orange.png$ 1.10.2 二叉树的层次遍历

$images\cherry_orange.png$ 1.10.3 二叉树的镜像翻转

$images\cherry_orange.png$ 1.10.4 二叉树的最大深度

$images\cherry_orange.png$ 1.10.5 二叉搜索树节点最小距离

$images\cherry_orange.png$ 1.10.6 二叉树重构从小到达按照->right情况

$images\cherry_orange.png$ 1.10.7 二叉搜索数的范围和

$images\cherry_orange.png$ 1.10.8 N叉树的前序遍历

$images\cherry_blue.png$ 1.11 递归

$images\cherry_orange.png$ 1.11.1 1+2...+n

$images\cherry_blue.png$ 1.12 并查集

$images\cherry_orange.png$ 1.12.1 并查集连通分量

$images\cherry_orange.png$ 1.12.2 并查集城市连通

$images\cherry_blue.png$ 1.13 堆栈

$images\cherry_orange.png$ 1.13.1 通过队列来实现栈

$images\cherry_orange.png$ 1.13.2 下一个更大元素 II

$images\cherry_orange.png$ 1.13.3 删除字符串中的所有相邻重复项

$images\cherry_orange.png$ 1.13.4 基本计算机

$images\cherry_orange.png$ 1.13.5 计算机

$images\cherry_orange.png$ 1.13.6 逆波兰表达式

$images\cherry_orange.png$ 1.13.7 接雨水

$images\cherry_orange.png$ 1.13.8 柱状图中最大矩形面积

$images\cherry_orange.png$ 1.13.9 反转每对括号间的子串

$images\cherry_blue.png$ 1.14 队列（or 优先队列）

$images\cherry_orange.png$ 1.14.1 最大平均通过率

$images\cherry_orange.png$ 1.14.2 最大的团队表现值

$images\cherry_orange.png$ 1.14.3 找出第K大的异或坐标值

$images\cherry_orange.png$ 1.14.4 1.2滑动窗口的最大值

$images\cherry_orange.png$ 1.14.5 二叉搜索数的范围和

$images\cherry_orange.png$ 1.14.6 员工的重要性

$images\cherry_blue.png$ 1.15 Hash查询匹配

$images\cherry_orange.png$ 1.15.1 猜灯谜

$images\cherry_orange.png$ 1.15.2 720. 词典中最长的单词

$images\cherry_blue.png$ 1.16 前缀树

$images\cherry_orange.png$ 1.16.1 实现Trie(前缀树)

$images\cherry_orange.png$ 1.16.2 添加与搜索单词 - 数据结构设计

$images\cherry_blue.png$ 1.17 位运算

$images\cherry_orange.png$ 1.17.1 比特位计数

$images\cherry_orange.png$ 1.17.2 不用加减乘除做加法

$images\cherry_orange.png$ 1.17.3 可被 5 整除的二进制前缀

$images\cherry_orange.png$ 1.17.4 汉明距离总和

$images\cherry_blue.png$ 1.18 二分法

$images\cherry_orange.png$ 1.18.1 在D天内送达包裹的能力

$images\cherry_orange.png$ 1.18.2 第一个错误的版本

$images\cherry_blue.png$ 1.19 数据结构性质

$images\cherry_blue.png$ 1.20 回溯法思想

$images\cherry_blue.png$ 1.21 字符串处理(模拟)

$images\cherry_orange.png$ 1.21.1 Excel 表列序号进制转换

$images\cherry_orange.png$ 1.21.2 838.推多米诺

$images\cherry_blue.png$ 1.22 模拟

$images\cherry_blue.png$ 1.23 数学定理

$images\cherry_orange.png$ 1.23.1 1828. 统计一个圆中点的数目

53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1
示例 3：

输入：nums = [0]
输出：0
示例 4：

输入：nums = [-1]
输出：-1
示例 5：

输入：nums = [-100000]
输出：-100000

提示：

1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
            '''
                动态规划，当前状态只依赖前一个状态，从而进行转移
                依赖前一个状态
                ('dp', 2, -2)
                ('dp', 3, 1)
                ('dp', 4, -2)
                ('dp', 5, 4)
                ('dp', 6, 3)
                ('dp', 7, 5)
                ('dp', 8, 6)
                ('dp', 9, 1)
            '''
        lens = len(nums)
        dp = nums[0]
        res = nums[0]

        for i in range(1,lens):
            print("dp",i+1,dp)
            dp = max(nums[i] + dp, nums[i])
            res = max(res,dp)
        return res