点击上方蓝字设为星标
东哥带你手把手撕力扣????
点击下方卡片即可搜索????
最大子数组问题和前文讲过的 经典动态规划：最长递增子序列 的套路非常相似，代表着一类比较特殊的动态规划问题的思路：
思路分析
其实第一次看到这道题，我首先想到的是滑动窗口算法，因为我们前文说过嘛，滑动窗口算法就是专门处理子串/子数组问题的，这里不就是子数组问题么？
但是，稍加分析就发现，这道题还不能用滑动窗口算法，因为数组中的数字可以是负数。
滑动窗口算法无非就是双指针形成的窗口扫描整个数组/子串，但关键是，你得清楚地知道什么时候应该移动右侧指针来扩大窗口，什么时候移动左侧指针来减小窗口。
而对于这道题目，你想想，当窗口扩大的时候可能遇到负数，窗口中的值也就可能增加也可能减少，这种情况下不知道什么时机去收缩左侧窗口，也就无法求出「最大子数组和」。
解决这个问题需要动态规划技巧，但是dp数组的定义比较特殊。按照我们常规的动态规划思路，一般是这样定义dp数组：
nums[0..i]中的「最大的子数组和」为dp[i]。
如果这样定义的话，整个nums数组的「最大子数组和」就是dp[n-1]。如何找状态转移方程呢？按照数学归纳法，假设我们知道了dp[i-1]，如何推导出dp[i]呢？
如下图，按照我们刚才对dp数组的定义，dp[i] = 5，也就是等于nums[0..i]中的最大子数组和：
那么在上图这种情况中，利用数学归纳法，你能用dp[i]推出dp[i+1]吗？
实际上是不行的，因为子数组一定是连续的，按照我们当前dp数组定义，并不能保证nums[0..i]中的最大子数组与nums[i+1]是相邻的，也就没办法从dp[i]推导出dp[i+1]。
所以说我们这样定义dp数组是不正确的，无法得到合适的状态转移方程。对于这类子数组问题，我们就要重新定义dp数组的含义：
以nums[i]为结尾的「最大子数组和」为dp[i]。
这种定义之下，想得到整个nums数组的「最大子数组和」，不能直接返回dp[n-1]，而需要遍历整个dp数组：
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
    res = Math.max(res, dp[i]);
}
return res;
依然使用数学归纳法来找状态转移关系：假设我们已经算出了dp[i-1]，如何推导出dp[i]呢？
可以做到，dp[i]有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。
如何选择？既然要求「最大子数组和」，当然选择结果更大的那个啦：
// 要么自成一派，要么和前面的子数组合并
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
综上，我们已经写出了状态转移方程，就可以直接写出解法了：
int maxSubArray(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    int[] dp = new int[n];
    // base case
    // 第一个元素前面没有子数组
    dp[0] = nums[0];
    // 状态转移方程
    for (int i = 1; i < n; i++) {
        dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
    }
    // 得到 nums 的最大子数组
    int res = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
}
以上解法时间复杂度是 O(N)，空间复杂度也是 O(N)，较暴力解法已经很优秀了，不过注意到dp[i]仅仅和dp[i-1]的状态有关，那么我们可以进行「状态压缩」，将空间复杂度降低：
int maxSubArray(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    // base case
    int dp_0 = nums[0];
    int dp_1 = 0, res = dp_0;

    for (int i = 1; i < n; i++) {
        // dp[i] = max(nums[i], nums[i] + dp[i-1])
        dp_1 = Math.max(nums[i], nums[i] + dp_0);
        dp_0 = dp_1;
        // 顺便计算最大的结果
        res = Math.max(res, dp_1);
    }

    return res;
}
最后总结
虽然说动态规划推状态转移方程确实比较玄学，但大部分还是有些规律可循的。
今天这道「最大子数组和」就和「最长递增子序列」非常类似，dp数组的定义是「以nums[i]为结尾的最大子数组和/最长递增子序列为dp[i]」。因为只有这样定义才能将dp[i+1]和dp[i]建立起联系，利用数学归纳法写出状态转移方程。
经典动态规划：戳气球问题
经典动态规划：0-1背包问题的变体
BFS 算法框架套路详解
历史文章摘要目录，建议收藏
＿＿＿＿＿＿＿＿＿＿＿＿＿
公众号：labuladong
B站：labuladong
知乎：labuladong
fucking-algorithm 项目在 Github 上已破 42k star，即将出版，公众号后台回复关键词「pdf」限时免费下载，回复「进群」可加入刷题群。东哥手把手带你撕 LeetCode，感受支配算法的快感～

				

对于python列表的理解可以和C语言里面的数组进行比较性的记忆与对照，它们比较相似，对于python里面列表的定义可以直接用方括号里加所包含对象的方法，并且python的列表是比较强大的，它包含了很多不同类型的数据：整型数字，浮点型，字符串以及对象等。接下来将介绍如何向列表里面加元素、删减列表中的一些元素、 获取列表里面的特定元素、列表分片、常用的列表操作符、其他常见列表操作函数。
4、列表分片
对于列表分片的含义需要明白，列表分片就是指将列表里面的一些列元素(不仅仅是某一个元素)进行获取或者得到：temp=List[A:B] 表示将m列表里从索引号位置为A开始的元素到B-1处元素之间的列表获取赋给temp。
temp = List[1:3]print(temp)
5、常用的列表操作符
首先定义两个列表list1和list2。
list1 = [1,2,3,4,5,6,7,8,9]list2 = [98,76,54,32,1]
1)+:它主要实现的是多个列表之间的拼接常见的列表操作符
list3 = list1 + list2print(list3)
2)*：主要实现的是列表的复制和添加
list3 = list1*3
3)比较>,<:>
list1 > list2
4)and等：；逻辑运算符，可以进行列表之间的逻辑判断
list1 > list2 and list2 > list3
6、其他常见列表操作函数
1)count(A)：输出元素A在列表list3里面出现的次数。
list3.count(1)
2)index(A)：输出元素A在列表m里面的索引位置号list3.index(A,a,b)：对于列表list3里面包含多个元素A时，输出在列表list3索引号a-b之间的特定索引号。
list3.index(1)
3)reverse()：将列表list3进行前后的翻转，前变后，后变前。
list3.reverse()print(list3)
4)sort()：将列表list3里面地数据进行从小到大的排列。
list3.sort()print(list3)
5)sort(reverse=True)：将列表list3里面地数据进行从大到小的排列。
list3.sort(reverse=True)print(list3)

对于python列表的理解可以和C语言里面的数组进行比较性的记忆与对照，它们比较相似，对于python里面列表的定义可以直接用方括号里加所包含对象的方法，并且python的列表是比较强大的，它包含了很多不同类型的数据：整型数字，浮点型，字符串以及对象等。接下来将介绍如何向列表里面加元素、删减列表中的一些元素、 获取列表里面的特定元素、列表分片、常用的列表操作符、其他常见列表操作函数、列表的拷贝。
我们首先定义一个列表。
List = [1,2,3,4.56,'xiaoming']
1、 向列表里面加元素。
向列表中增加元素有三种方法：
第一种，append()函数。对于列表的操作主要实现的是在特定的列表最后添加一个元素，并且只能添加一个元素，并且只能在列表最后；【向列表最后添加一个元素“student”】。
List.append("student")
第二种，extend()函数。对于列表的操作主要实现的是对于特定列表的扩展和增长，可以一次添加多个元素，不过也只能添加在列表的最后；【向列表最后添加元素“A”、"B"、"C"】。
 List.extend(['A','B','C'])
第三种，insert()函数对于列表的操作主要是在列表的特定位置添加想要添加的特定元素，比较常用。【向列表第一个位置添加元素“WelcomeToPython"】。
List.insert(0,'WelcomeToPython')
2、 删减列表中的一些元素。
与之前python列表的添加元素相对，删减列表里面的一些元素也有三种方法：
第一种，remove()函数，移除掉列表里面的特定元素；
List.remove("xiaoming")
第二种，操作语句del，删除掉列表里面的索引号位置为n的元素；
del List[0]
第三种，pop()函数，将列表的最后一个元素返回，并且在此基础上进行删除掉。
temp = List.pop()
3、 获取列表里面的特定元素。
temp=List[n] %获取List列表第n+1位置处的元素。
temp = List[1]print(temp)

对于python列表的理解可以和C语言里面的数组进行比较性的记忆与对照，它们比较相似，对于python里面列表的定义可以直接用方括号里加所包含对象的方法，并且python的列表是比较强大的，它包含了很多不同类型的数据：整型数字，浮点型，字符串以及对象等。接下来将介绍如何向列表里面加元素、删减列表中的一些元素、 获取列表里面的特定元素、列表分片、常用的列表操作符、其他常见列表操作函数、列表的拷贝。
我们首先定义一个列表。
List = [1,2,3,4.56,'xiaoming']
1、 向列表里面加元素。
向列表中增加元素有三种方法：
第一种，append()函数。对于列表的操作主要实现的是在特定的列表最后添加一个元素，并且只能添加一个元素，并且只能在列表最后；【向列表最后添加一个元素“student”】。
List.append("student")
第二种，extend()函数。对于列表的操作主要实现的是对于特定列表的扩展和增长，可以一次添加多个元素，不过也只能添加在列表的最后；【向列表最后添加元素“A”、"B"、"C"】。
 List.extend(['A','B','C'])
第三种，insert()函数对于列表的操作主要是在列表的特定位置添加想要添加的特定元素，比较常用。【向列表第一个位置添加元素“WelcomeToPython"】。
List.insert(0,'WelcomeToPython')
2、 删减列表中的一些元素。
与之前python列表的添加元素相对，删减列表里面的一些元素也有三种方法：
第一种，remove()函数，移除掉列表里面的特定元素；
List.remove("xiaoming")
第二种，操作语句del，删除掉列表里面的索引号位置为n的元素；
del List[0]
第三种，pop()函数，将列表的最后一个元素返回，并且在此基础上进行删除掉。
temp = List.pop()
3、 获取列表里面的特定元素。
temp=List[n] %获取List列表第n+1位置处的元素。
temp = List[1]print(temp)