首页 > 代码库 > 求一个数组的子数组的最大和

求一个数组的子数组的最大和

如题:求一个数组的子数组的最大和,要求O(n)时间复杂度。

由于有了O(n)时间复杂度的限制,所以暴力求解的O(n^2)方法肯定不行。再考虑递归求一个数组a[n]的子数组的最大和,可以分解为a[i]子数组的最大和以及a[n-i-1]之间的某种情况

  • a[n]的子数组最大和等于a[i]子数组的最大和;
  • a[n]的子数组最大和等于a[n-i-1];
  • a[n]的子数组最大和跨a[i]和a[n-i-1];

递归实现的时间复杂度为O(nlg(n))。最后考虑时间复杂度为O(n)的动态规划实现。

/** * Created by elvalad on 2014/12/4. * 求一个数组的子数组的最大和 */import java.util.ArrayList;import java.util.Scanner;public class MaxSubArray {    /* 暴力遍历所有子数组的和 */    public static int maxSubArray1(ArrayList<Integer> a) {        int sum = 0;        int max = Integer.MIN_VALUE;        for (int i = 0; i < a.size(); i++) {            sum = 0;            for (int j = i; j < a.size(); j++) {                sum += a.get(j);                if (sum > max) {                    max = sum;                }            }        }        return max;    }    /* 递归实现 */    public static int maxSubArray2(ArrayList<Integer> a, int low, int high) {        int max = Integer.MIN_VALUE;        int max1 = Integer.MIN_VALUE;        int max2 = Integer.MIN_VALUE;        int max3 = Integer.MIN_VALUE;        int max4 = Integer.MIN_VALUE;        int sum = 0;        if (low < high) {            int mid = low + (high - low)/2;            /* 最大子数组为左半部分的子数组最大值 */            max1 = maxSubArray2(a, low, mid);            /* 最大子数组为右半部分的子数组最大值 */            max2 = maxSubArray2(a, mid + 1, high);            /* 最大子数组跨越mid元素,所以最大值必定为mid向左的最大值加上mid向右的最大值 */            for (int i = mid; i >= low; i--) {                sum += a.get(i);                if (sum > max3) {                    max3 = sum;                }            }            sum = 0;            for (int i = mid + 1; i <= high; i++) {                sum += a.get(i);                if (sum > max4) {                    max4 = sum;                }            }            return Math.max(Math.max(max1, max2), (max3 + max4));        } else {            return a.get(0);        }    }    /* 动态规划 */    public static int maxSubArray3(ArrayList<Integer> a) {        int max = Integer.MIN_VALUE;        int sum = 0;        /* 每个元素更新sum的值,当sum<0时清零,同时如果sum>max时更新max */        for (int i = 0; i < a.size(); i++) {            sum += a.get(i);            if (sum > max) {                max = sum;            } else if (sum < 0) {                sum = 0;            }        }        return max;    }    public static void main(String[] args) {        Scanner scan = new Scanner(System.in);        ArrayList<Integer> array = new ArrayList<Integer>();        while (scan.hasNext()) {            array.add(scan.nextInt());        }        System.out.println("The max sub array is :" + maxSubArray1(array));        System.out.println("The max sub array is :" + maxSubArray2(array, 0, array.size()-1));        System.out.println("The max sub array is :" + maxSubArray3(array));    }}

求一个数组的子数组的最大和