题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？

思路大概有3种。

1. 暴力穷举法
2. 分治递归
3. 动态规划

import java.util.Scanner;

public class FindGreatestSumOfSubArray {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("the size of array:");
        int n = scanner.nextInt();
        int[] array = new int[n];
        System.out.println("input the array:");
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }
        System.out.println("max sumOfSubArray is:" + FindGreatestSumOfSubArray(array));
    }

    // 方法1：暴力穷举法
    public static int FindGreatestSumOfSubArray(int[] array) {
        int len = array.length;
        if (len == 0) {
            return 0;
        }
        int maxSum = array[0];
        for (int i = 0; i < len - 1; i++) {
            int partSum = array[i];
            if (partSum > maxSum) {
                maxSum = partSum;
            }
            for (int j = i + 1; j < len; j++) {
                partSum += array[j];
                if (partSum > maxSum) {
                    maxSum = partSum;
                }
            }
        }
        return maxSum;
    }

    // 方法2：分治递归方法 o(N*log2N)
    public static int FindGreatestSumOfSubArray1(int[] array) {
        int len = array.length;
        if (len == 0) {
            return 0;
        }
        return maxSumOfSubArray(array, 0, len - 1);
    }

    // 递归求解
    public static int maxSumOfSubArray(int[] array, int left, int right) {
        if (left == right) {
            return array[left];
        }
        int mid = (left + right) / 2;
        // 前半部分最大子数组
        int leftMaxSub = maxSumOfSubArray(array, left, mid);
        // 后半部分最大子数组
        int rightMaxSub = maxSumOfSubArray(array, mid + 1, right);
        // 中点向左最大子数组
        int maxOfMidLeft = maxSubArray(array, mid, left);
        // 中点向右最大子数组
        int maxOfMidRight = maxSubArray(array, mid + 1, right);
        int midMaxSub = maxOfMidLeft + maxOfMidRight;
        // 返回3种情况的最大值
        int maxSub = leftMaxSub > rightMaxSub ? leftMaxSub : rightMaxSub;
        return maxSub > midMaxSub ? maxSub : midMaxSub;

    }

    // 求left到right的最大子数组的最大值
    public static int maxSubArray(int[] array, int left, int right) {
        int maxSub = array[left];
        if (left == right) {
            return maxSub;
        }
        int tempSub = maxSub;
        int flag = left < right ? 1 : -1;
        if (flag == 1) {
            for (int i = left + 1; i <= right; i++) {
                tempSub += array[i];
                if (tempSub > maxSub) {
                    maxSub = tempSub;
                }
            }

        } else {
            for (int i = left - 1; i >= right; i--) {
                tempSub += array[i];
                if (tempSub > maxSub) {
                    maxSub = tempSub;
                }
            }
        }
        return maxSub;
    }

    // 动态规划 O(N)复杂度
    // all[i-1] =
    // max{array[i-1],array[i-1]+Start[i],all[i]},其中Start[i]是指array[i],...,array[len-1]中从array[i]开始的最大子数组
    // all[i]指array[i],...,array[len-1]中的最大子数组之和
    public static int FindGreatestSumOfSubArray2(int[] array) {
        int len = array.length;
        if (len == 0) {
            return 0;
        }
        int[] all = new int[len];
        int[] start = new int[len];
        all[len - 1] = array[len - 1];
        start[len - 1] = array[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            start[i] = Math.max(start[i + 1] + array[i], array[i]);
            all[i] = Math.max(start[i], all[i + 1]);
        }
        return all[0];
    }

    // 动态规划的改进 o(1)的空间
    public static int FindGreatestSumOfSubArray3(int[] array) {
        int len = array.length;
        if (len == 0) {
            return 0;
        }
        int all = array[len - 1];
        int start = array[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            start = Math.max(start + array[i], array[i]);
            all = Math.max(start, all);
        }
        return all;
    }
}