数组中最大子数组和之连续子数组和

前言一、案例

1、数组中最大子数组和2、示例二、题解1、暴力法2、利用已知条件 总结参考文献

暴力解通常不能满足时间复杂度的要求，必须抓住已知条件来寻找低时间复杂度的解题方式。

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

直接以O(n²)的复杂度寻找最大和。

//最大子数组和
public class MaxSubArray {
    public int maxSubArray(int[] nums) {
        //ON方复杂度来遍历出一个最大值
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            if (max < sum) max = sum;
            for (int j = i + 1; j < nums.length; j++) {
                sum += nums[j];
                if (max < sum) max = sum;
            }
        }
        return max;
    }

连续子数组，有正有负，当左缀和小于等于0是就没有加下去的必要了，相当于把暴力法的第一层for往后面求和大于0的地方提，把暴力法的第二层for中的控制条件往前提到和小于等于0的地方。

//认真找出其中的规律和联系，不要被不严谨的我以为作为指导方针。
    public int maxSubArray(int[] nums) {
        //当左缀和小等等于0时，左缀数组继续加下去没有意义，则需要定义新的起点，开始累加，把每向前遍历一步就作为一个终点，记录此时的和是否为最大值。
        int res = nums[0];
        int sum = 0;
        for (int num : nums) {
            sum += sum > 0 ? num : num - sum;
            res = res < sum ? sum : res;
        }
        return res;
    }

1）利用已知的条件联系题解的方向做一个时间空间复杂度上的简化。
2）专注思考效率高，认真找出其中的规律和联系，不要被不严谨的我以为(不专注的体现)作为指导方针。
3）实在做不来(在专注思考的前提下)，看题解，此时不浪费宝贵的时间；也不要思考完了不上手敲代码，而直接去对题解，此时浪费题源。

[1]LeetCode 原题