（java版剑指offer）JZ42 连续子数组的最大和(三种方法：暴力破解+动态规划+优化动态规化)

//方法一：暴力破解
//分析：//外循环，子数组的起始位置
	   //内循环，子数组的组合，比较找出子数组的最大值

//时间复杂度：n^2
//空间复杂度：1
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        //暴力破解
        //定义两个变量，子数组的和sum，和最大值max
        int sum = 0;
        int max = array[0];
        //外循环，子数组的起始位置
        for(int i=0; i<array.length; i++){
            //最大值在循环中初始化
            sum = 0;
            //内循环，子数组的组合，比较找出子数组的最大值
            for(int j=i; j<array.length; j++){
                sum +=array[j];
                max = Math.max(max, sum);
            }
        }
        return max;        
    }
}

//方法一：暴力破解
//分析：//外循环，子数组的起始位置
       //内循环，子数组的组合，比较找出子数组的最大值
//时间复杂度：n^2
//空间复杂度：1
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        //动态规划
        //定义一个数组q，用于在q[i]中存放q[i-1] + array[i]与array[i]比较后的最大值
        //若q[i-1] + array[i] < array[i]     ，那就以array[i]开始重新找连续几个数的最大值
        //只要找出数组q存储的最大值，就能找到的连续几个数的最大值，
        int[] q = new int[array.length];
        int max = //方法二：优化动态规划
//分析：不需要定义新数组，只需将每次的最大值暂存就可以了
//时间复杂度：n
//空间复杂度：1
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max = array[0];	
        int sum = array[0];		//不需要定义新数组，只需将每次的最大值暂存就可以了
        
        for(int i=1; i<array.length; i++){
            sum = Math.max(sum + array[i], array[i]);
            max = Math.max(max, sum);
        }
        return max;
    }
}
;
        q[0] = array[0];
        
        for(int i=1; i<array.length; i++){
            q[i] = Math.max(q[i-1] + array[i], array[i]);
            max = Math.max(max, q[i]);
        }
        return max;
    }
}

//方法二：动态规划
//时间复杂度：n
//空间复杂度：n
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        //动态规划：分析如下
        //定义一个数组q，用于在q[i]中存放q[i-1] + array[i]与array[i]比较后的最大值
        //若q[i-1] + array[i] < array[i]     ，那就以array[i]开始重新找连续几个数的最大值
        //只要找出数组q存储的最大值，就能找到的连续几个数的最大值，
        int[] q = new int[array.length];
        int max = //方法二：优化动态规划
//分析：不需要定义新数组，只需将每次的最大值暂存就可以了
//时间复杂度：n
//空间复杂度：1
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max = array[0];	
        int sum = array[0];		//不需要定义新数组，只需将每次的最大值暂存就可以了
        
        for(int i=1; i<array.length; i++){
            sum = Math.max(sum + array[i], array[i]);
            max = Math.max(max, sum);
        }
        return max;
    }
}
;
        q[0] = array[0];
        
        for(int i=1; i<array.length; i++){
            q[i] = Math.max(q[i-1] + array[i], array[i]);
            max = Math.max(max, q[i]);
        }
        return max;
    }
}

//方法二：优化动态规划
//分析：不需要定义新数组，只需将每次的最大值暂存就可以了
//时间复杂度：n
//空间复杂度：1
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max = //方法二：优化动态规划
//分析：不需要定义新数组，只需将每次的最大值暂存就可以了
//时间复杂度：n
//空间复杂度：1
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max = array[0];	
        int sum = array[0];		//不需要定义新数组，只需将每次的最大值暂存就可以了
        
        for(int i=1; i<array.length; i++){
            sum = Math.max(sum + array[i], array[i]);
            max = Math.max(max, sum);
        }
        return max;
    }
}
;	
        int sum = array[0];		//不需要定义新数组，只需将每次的最大值暂存就可以了
        
        for(int i=1; i<array.length; i++){
            sum = Math.max(sum + array[i], array[i]);
            max = Math.max(max, sum);
        }
        return max;
    }
}