算法test005

求最大子数组和。输入一个整形数组，数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和，求所有子数组和的最大值。
例：输入的数组为1,-2，3,10，-4,7，2,-5。和最大的子数组为3,10，-4，7,2。因此输出该子数组的和为18。
代码如下：
方法一（暴力法）
public class test005 {
public static void main(String[] args) {
int[] a = new int[]{1,-2, 3,10, -4, 7, 2, -5};
int res = maxSum(a);
System.out.println("所有子数组和的最大值为："+res);
}

private static int maxSum(int[] a) {
    if(a==null || a.length ==0){
        return 0;
    }
    int max = a[0];
    for(int i=0; i<a.length; i++){
        int temp = 0;
        for(int j=i; j<a.length; j++){
            temp+=a[j];
            if(temp>max){
                max = temp;
            }
        }
    }
    return max;
}

}
算法复杂度为O(n^2)
方法二
public class test005 {
public static void main(String[] args) {
int[] a = new int[]{1,-2, 3,10, -4, 7, 2, -5};
int res = maxSum2(a);
System.out.println("所有子数组和的最大值为："+res);
}

public static int maxSum2(int[] a){
    if(null == a || a.length == 0){
        return 0;
    }

    int tmp = a[0];
    int max = a[0];
    for(int i = 1; i < a.length; i++){
        if(tmp < 0){
            tmp = 0;
        }

        tmp += a[i];
        max = Math.max(max, tmp);
    }

    return max;
}

}
算法复杂度为O(n)
方法三（分治法、dp解法）
public class test005 {
public static void main(String[] args) {
int[] a = new int[]{1,-2, 3,10, -4, 7, 2, -5};
int res = maxSum3(a, 0, a.length-1);
System.out.println("所有子数组和的最大值为："+res);
}

public static int maxSum3(int[] a, int left, int right){
    if(left == right){
        return a[left];
    }else{
        int mid = left + (right - left) / 2;
        int leftMaxSum = maxSum3(a, left, mid);
        int rightMaxSum = maxSum3(a, mid + 1, right);
        int crossMaxSum = crossMaxSum(a, left, mid, right);

        return Math.max(Math.max(leftMaxSum, rightMaxSum), crossMaxSum);
    }
}

public static int crossMaxSum(int[] a, int left, int mid, int right){
    int leftMaxSum = 0;
    int temp = 0;
    for(int i = mid; i >= left; i--){
        temp += a[i];
        leftMaxSum = Math.max(leftMaxSum, temp);
    }


    temp = 0;
    int rightMaxSum = 0;
    for(int i = mid + 1; i <= right; i++){
        temp += a[i];
        rightMaxSum = Math.max(rightMaxSum, temp);
    }

    return leftMaxSum + rightMaxSum;
}

}
时间复杂度：O(nlogn)
欢迎交流指正~