最近很慌自己算法这一块，想着去领扣上练一下，然后遇到了一道最大连续子数组的问题，感觉似曾相识，就是想不起来怎么做。虽说可以用暴力法来解，但是那样的话就没有什么练习的必要了。
题目大致如下：
给定一个数组，求它的最大连续子数组，这里的最大指的是子数组之和最大，数组中可能有正数、负数或者0。
因为之前接触过一点动态规划，上网找了一下这种题的动规解法，开始总觉得思维有点绕不过来，直到仔细阅读找到的资料，发现问题出在了没有好好阅读人家设定的思维。
动规解法的思维是假设某个元素为最大子数组的最后一位，也就是说，这个元素要么和它前一个元素连在一起，可能还有其他元素共同组成子数组，要么自己组成子数组。
仔细想一下，设定的这种思维并不违背最终结果，因为最终结果至少要包含一个元素，而最终子数组的最后一位一定来自于给定数组。
首先来考虑一下比较简单也比较极端的一种情况，如果数组中只有一个元素：
这种情况下，最大连续子数组就是这个元素本身。但如果按照前面设定的思维来思考，应该是这样的，假设array[0]为最大子数组的最后一位，那么这个子数组要么是它自己，要么是它与它前一个元素连在一起，可能还有其他元素共同组成子数组。但是，它的前面并没有元素，所以只能是它自身。也就是说，这个结果就是两种可能性中的最优解，就是所谓的局部最优解。
那么如果数组的末位再加入一个元素呢？
设定array[1]为最大子数组的最后一位（实际上不一定是），那么这个子数组要么是它自己，要么是它与它前一个元素连在一起，可能还有其他元素共同组成子数组。
有且只有这两种情况，因为题目规定子数组必须连续。
它的前一个元素为array[0]，也就是数组中第一个元素。
那么现在针对设定array[1]为最大子数组的最后一位的情况，可以求出两个结果，结果一为array[1]自身，结果二为array[1]与array[0]以及可能还有（假设可能）array[0]前面的元素组成。
那么又可以得出两个结果，结果一为array[1]自身，结果二为array[1]加前一次计算的局部最优解，因为加前一次的局部最优解就满足了，array[1]与它的前一位连续的这个条件。
当然这只是原因之一，另外一个主要的原因就是，前一次计算的局部最优解还可以有另一个定义，与当前元素连续的最大子数组之和。
找了几个网上的解法，是将每一次的局部最优解都记录下来，最后一起比较。
但是实际上只需要记录两个值，最大局部最优解（最终结果），前一次局部最优解（用于本次计算）。
然后我稍微自己改造了一下：
static int maxSubArray(int[] nums) { if (nums.length == 0 || nums == null) return 0; int[] arr = new int[]{nums[0], nums[0]}; for (int i = 1; i < nums.length; i++) { arr[1] = Math.max(nums[i], nums[i] + arr[1]); arr[0] = Math.max(arr[0], arr[1]); } return arr[0]; }
最后，感觉这个思路挺绕的... ...