/** * 求最大子序列和的问题 * 给定（可能有负数）一组整数值，求这组子序列的最大值 * @author breeze * */public class MaxSubSum {    //时间复杂度为N^2    public static int maxSubSum2(int[] a){        int maxSum = 0;        for(int i = 0 ;i < a.length;i++){            int thisSum = 0;            for(int j =i;j < a.length;j++){                thisSum += a[j];                if(thisSum > maxSum){                    maxSum = thisSum;                }            }        }        return maxSum;    }        //求最大子序列和的最优解(最简洁版，但不好理解，下面那个解释版好理解)    public static int maxSubSum4(int[] a){        int maxSum = 0;        int thisSum = 0;        for(int i = 0;i<a.length;i++){            thisSum += a[i];            if(thisSum > maxSum){                maxSum = thisSum;            }else if(thisSum < 0){                thisSum = 0;            }        }        return maxSum;    }    //最大子序列和的最优解的解释版    /**     * currSum是以当前元素为结尾的连续子数组之和，maxSum是全局的最大子数组之和     * 事实上，当从前往后扫描一个数组时，对于第i个元素，有两种选择，要么放入前面已经找到的子数组，要么不放入，而是作为新的子数组的第一个元素     * 如果currSum>0，则令currSum加上a[i];     * 如果currSum<0，则置currSum等于当前元素，即currSum = a[i]     * 这就相当于，如果currSum(i)是以i结尾的最大连续子数组的和，那么currSum(i) = max{0,currSum(i-1)+a[i]}     * 如果maxSum<currSum，则更新maxSum=currSum；否则maxSum保持原值，不更新     * 举个例子：{1，-2,3,10，-4,7,2，-5}     * currSum:0->1->-1->3->13->9->16->18->13     * maxSum: 0->1-> 1->3->13->13->16->18->18     * @param a     * @return     */    public static int maxSubSum(int[] a){        int maxSum = a[0];//数组全为负数的情况下，返回最大数        int currSum = 0;        for(int i = 0;i<a.length;i++){            if(currSum >= 0){                currSum += a[i];            }else{                currSum = a[i];            }                        if(maxSum < currSum){                maxSum = currSum;            }        }        return maxSum;    }    /**     * 延伸一：求出最大连续子数组和，同时要求输出所求子数组的开始位置和结束位置     *      * @param a     * @return     */    public static int maxSubSumIndex(int[] a){        int maxSum = a[0];//数组全为负数的情况下，返回最大数        int currSum = 0;        int start = 0;        int end = 0;        for(int i = 0;i<a.length;i++){            if(currSum >= 0){                currSum += a[i];            }else{                currSum = a[i];                start = i;                end = i;//每次重置以当前元素为结尾的连续子数组之和时，需要更新开始和结束位置。            }                        if(maxSum < currSum){                maxSum = currSum;                end = i;//每次全局最大值变动时，需要更新结束位置            }        }        System.out.println("start："+start+",end："+end);        return maxSum;    }                public static void main(String[] args) {        int[] a = {-2,11,-4,13,-5,-2,9};//        int result = maxSubSum2(a);        int result = maxSubSumIndex(a);        System.out.println(result);    }}