一、相关概念

子数组：数组中连续出现的数

二、题目

题目

思路

1. 枚举O(nnn)

将数组所有的子数组列举出来，分别计算子数组和，最终得到最大的。

/**
     * 把数组的所有子数组都求出来，然后求出最大的和
     * O(n*n*n)
     * @param arr
     * @return
     */
    public int f(int[] arr){
        int max=Integer.MIN_VALUE;
        for(int i=0;i<arr.length;i++){
            for(int j=i;j<arr.length;j++){
                // [i,j]数组
                int sum=0;
                for(int t=i;t<=j;t++){
                    sum+=arr[t];
                }
                if(sum>max){
                    max=sum;
                }
            }
        }
        return max;
    }

2. 优化了的枚举法O(nn)

sum[i,j]=sum[i,j-1]+arr[j]；利用已经计算出来的子数组和，省去计算sum[i,j-1]的时间。

/**
     * 把数组的所有子数组都求出来，
     * 计算以i为左边界的子数组和时，可以利用上一个子数组的计算结果
     * O(n*n)
     * @param arr
     * @return
     */
    public int f2(int[] arr){
        int max=Integer.MIN_VALUE;
        for(int i=0;i<arr.length;i++){
            // 以i开头的子数组
            int sum=0;
            // 以i开头的子数组右边界
            for(int j=i;j<arr.length;j++){
                sum+=arr[j];
                if(sum>max){
                    max=sum;
                }
            }
        }
        return max;
    }

3. 动态规划O(n)

思考的时候从后往前倒推，写代码的时候从前往后计算（保存中间计算结果）。

• 按照给出的顺序逐个试探（选或不选）
• 将中间结果保存在数组中
• 返回最终结果
  end[i]：表示在数组[0,i]范围内，以arr[i]结尾的最大子数组和
  all[i]：表示在数组[0,i]范围内，最大子数组和
  假设现在要计算all[i]：将arr[i]作为重点关注对象，选或不选
  
  思考时逆着推导

正着写代码

public int f3(int[] arr){
        return f3(arr,arr.length-1);
    }
    
    /**
     * 动态规划
     * O(n)，数组中[0,n]范围内的最大子序和
     * @param arr
     * @return
     */
    private int f3(int[] arr,int n){
        // 以arr[i]为结尾的子数组最大和
        int[] end=new int[arr.length];
        // [0,i]范围内的数组成的子数组最大和
        int[] all=new int[arr.length];
        end[0]=arr[0];
        all[0]=arr[0];
        for(int i=1;i<=n;i++){
            // 和最大子数组选arr[i]
            end[i]=Math.max(end[i-1]+arr[i],arr[i]);
            int A=end[i];
            // 不选
            int B=all[i-1];
            all[i]=Math.max(A,B);
        }
        return all[n];
    }

4. 优化了的动态规划

上述动态规划方法中，每次只用到end[i-1]和all[i-1]，而不是整个数组中的值，因此可以定义两个变量来保存end[i-1]与all[i-1]的值，并可以反复利用，这样在保证时间复杂度的同时可降低空间复杂度。

/**
     * 动态规划
     * O(n)，数组中[0,n]范围内的最大子序和
     * @param arr
     * @return
     */
    private int f4(int[] arr,int n){
        int preEnd=arr[0];
        int preAll=arr[0];
        for(int i=1;i<=n;i++){
            // 和最大子数组选arr[i]
            preEnd=Math.max(preEnd+arr[i],arr[i]);
            int A=preEnd;
            // 不选
            int B=preAll;
            preAll=Math.max(A,B);
        }
        return preAll;
    }

参考文献

Leetcode_最大子序和
Leetcode题解