LeetCode 学习01 最大子序和（难度：简单）

题目

    给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    示例:
    输入: [-2,1,-3,4,-1,2,1,-5,4],
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

    链接：https://leetcode-cn.com/problems/maximum-subarray

自己的思路

1. 暴力解法
       列出所有的子数组及和，max出最大的。需要两层循环，for 循环子数组长度，for循环 固定长度的子数组。
       n(n-1)/2 次，所以时间复杂度是O($n^2$). 空间上需要保存每次的结果，也是O($n^2$).
2. 滑动窗保存结果
       需要两层循环，for 循环子数组长度，for循环 固定长度的子数组。但是在内层循环中，只保留最大的那个数组和。
       时间复杂度 O($n^2$). 空间复杂度 O($n$).
3. 利用正数索引
       求和最大，所以正数越多越好，因此取出所有正数的索引，以索引为节点遍历求和。仍需要两层循环，但是每层循环数目比n小。
       如果正数的个数为 $n_{+}$, 间复杂度 O($n_{+}^2$). 空间复杂度 O($n_{+}$).

    师父留了思考题是O($n$)，想了想应该是每一步做了什么操作，囊括了之前这个每次需要到这个位置的情况，但是再往下想，就想不出来了。

参考答案

    对于O($n$)思考无果，查看了官方答案。官方答案给出的是O($n$)，我认为这个关键在于“丢弃”，如果这个元素$i$之前的数列之和是小于零的，那么肯定是不利于“和最大”，所以果断丢弃。这也就是我所卡住的地方，而我所卡住的原因是认为需要囊括这个位置所有的情况，那么就要包含不同的数列长度情况、向前还是向后，然后就会觉得一团乱，无从下手。而贪心算法只对过去的结果、当下的结果进行选择，未来的情况不知道，所以不考虑。因此节省了时间复杂度，由于每次只保留1个结果，所以空间复杂度也减小了。
    贪心算法：用一个循环来遍历整个数列，在每个索引处，只保留当前的和最大值。如果当前索引（0至$i-1$）的和是小于零的，则丢弃，$i$处只包括元素$i$。如果元素$i$比上一步的结果大，则进行替换，否则仍保留上一次结果，然后继续$i+1$.
    动态规划：我觉得答案给出的动态规划，是可以在原数列的空间上进行修改，不需要占用新的内存空间。用一个循环来遍历整个数列，在每个索引处，如果上一个数是整数，那么$i$的值就等于$i$+$i-1$，所以原来的数列就变成了当索引进行到$i$时，留下$i$还是$i$+之前的和，其实也就是之前贪心算法的选择保留到了每个索引处，最后用max函数求出最大值，代替了贪心算法中每一步都要进行比较。

1. 贪心算法

2.动态规划

用时 1h40m.

文章来源: dujiahei.blog.csdn.net，作者：dujiahei，版权归原作者所有，如需转载，请联系作者。

原文链接：dujiahei.blog.csdn.net/article/details/106607564