连续子数组的最大和

java

一个比较实用&简单的思想

分析得:

• 题目的意思其实是求最大连续子序列 求最大子序列有一个规则: 负数和任何数相加只会越来越小
• a[] = {-1,1,3,-20,4,-1,4}
• 时间复杂度为O(n)

解法一

public int FindGreatestSumOfSubArray(int[] array) {
        int length = array.length;
        int max = array[0];  //设最大的子序列为 a[0]
        int newMax = array[0];  //记录新的子序列的和
        for (int i = 1; i < length; i++) {    //a[] = {-1,1,3,-20,4,-1,4}
            if (newMax < 0) {             
                newMax = 0;     //判断子序列如果小于0  则从下一个位置开始计算最大值   例如:第一个数为a[0]=-1 则从a[1]开始计算
            }
            newMax += array[i];   //子序列的和
            if (newMax > max) {  
                max = newMax;
            }
        }
        return max;
    }

解法二: 一个比较常规的方法

遍历数组, 记录每一种可能
时间复杂度O(N^2)

    public int FindGreatestSumOfSubArray(int[] array) {
        int length = array.length;
        int max = array[0];
        for (int i = 0; i < length; i++) {   //记录其实位置
            int temp = 0;
            for (int j = i; j < length; j++) {  //从起始位置开始往后累加  记录每一次的结果  然后和最大值比较
                temp += array[j];
                if (temp > max) {
                    max = temp;
                }
            }
        }
        return max;
    }