最大子序和

问题描述

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

解题思路

我最开始做这道题的时候是没有思路的，或者说，思路非常混乱，想到了双指针，想到了for循环，但是具体怎么做却没有一个清晰的思路。然后看了官方的答案才懂。

思路一：动态规划

class Solution {
    public int maxSubArray(int[] nums) {
        //储存子数组的和。（当前的和）
        int cur = 0;
        //和最大的子数组。（最大的和）
        int max = nums[0];
        for(int num:nums){
            //如果之前的子数组小于num，那么就抛弃之前的子数组，从num重新算起
            cur = Math.max(num,cur+num);
            //比较每次生成的子数组，找到最大的那一个
            max = Math.max(max,cur);
        }
        return max;
    }
}

首先for循环遍历数组的每个元素，使用cur这个变量盛放当前子数组的和，与下一个遍历的数组元素进行比较，如果当前子数组的和比下一个数组元素还小，那么就舍弃当前子数组，从下一个元素开始，重新创建子数组。

max是和最大的子数组，即将新生成的子数组与之前生成的子数组的和进行比较，将大的赋值给max，那么最后就可以得到最大的那个子数组和。

我想这个思路叫动态规划的原因是由于cur和max的两个值在每次循环中是不断变化的吧。

该思路的时间复杂度为O(n)，空间复杂度为O(1)。

思路二：分治法（以后更新）