继续打卡算法题，今天学习的是LeetCode第53题最大子数组和，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。
分析一波题目
本题可以使用最笨的办法，把所有连续组合求出来，最后将计算得到最大和的组合。但是可以借助一些技巧，避免保存所有的组合，我们其实可以只要存一个最大的组合值就可以，每求一个组合就和最大值比较，如果当前组合大于最大值，就更新最大组合值。
其中一个比较好的解法思路是：
每次以某个元素为组合的最后一个元素，计算当前组合的和，如果大于之前最大的组合和，那么更新最大的组合和。
以[-2,1,-3,4,-1,2,1,-5,4]为例，
1、先求-2结尾的组合，最大组合和是-2
2、求1结尾的组合，最大组合和是1
3、求-3结尾的组合，最大组合和是1
....以此类推
本题解题技巧
1、每得到一个组合，就更新最大组合和，不用等所有组合求出来后再计算最大组合和
2、本题以每个元素结尾的组合，组合最大值要么是它本身，要么是之前的最大值加上它本身
3、其实这就是动态规划思想。动态规划就是解决最值问题的。
编码解决
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
int pre = nums[0];
for(int i=1; i<nums.length;i++) {
//每次求以当前下标结尾的表示的最大子树组和
//第i个结尾的 最大子数组和
int temp = pre + nums[i];
//求当前节点最大和
pre = Math.max(temp, nums[i]);
//求全局最大和
max = Math.max(pre, max);
}
return max;
}
}
总结
哈哈，本题采用动态规划思路虽然降低了朴素解法的复杂度，但是时间复杂度还需要O(n)。
题目最后要求使用使用分而治之思想，但是作者认为本题解决比分而治之思想更简单易懂。
