第一次课实验报告

题面

给定一个数组，求其各子数组和的最大值。

思路

枚举每一个子数组（共有 $O(n^2)$ 个），然后求出每一个子数组的和，最后取所有子数组和的最大值。总时间复杂度 $O(n^3)$。

考虑到从 $i$ 到 $j$ 的子数组（含两端）的和为

$$\sum\limits_{i\leq n\leq j}a_n = \sum\limits_{0\leq n\leq j}a_n - \sum\limits_{0\leq n\leq i}a_n$$

注意到我们对于每一个 $p_i = \sum\limits_{0\leq n\leq i}a_n$ 只需要计算一次即可。故计算出该子数组的前缀和：

private static int[] getPrefixSum(int[] array) {
    int[] prefixSum = Arrays.copyOf(array, array.length);
    for (int i = 1; i < prefixSum.length; i++) {
        prefixSum[i] += prefixSum[i-1];
    }
    return prefixSum;
}

我们只需要找出这样的一对 $i,j$ 使得 $p_j - p_i$ 最大 且 $j\ge i$ 即可。故我们只需要对每一个 $p_i$ 枚举 $j$。总时间复杂度 $O(n^2)$。

注意到对于每个 $p_i$，其对应的使 $p_j - p_i$ 最大的 $j$ 大致相同。故我们只需要求 $p_i$ 的后缀最大值，并对每一个 $p_i$ 比对其对应的后缀最大值，无需知道具体的 $j$。总时间复杂度 $O(n)$。

代码

import java.util.Arrays;
import java.util.Scanner;

public class MaxIntervalArray {

    public static void main(String[] args) {
        int[] array = new int[100050];
        array = getArrayFromInput();
        int Result = maxIntervalArray(array);
        System.out.println(Result);
    }

    public static int[] getArray() {
        // Get example array through in-program definition
        int[] tempArray = {1,2,-3,-4,1,100,-99,43,-25,26};
        return tempArray;
    }

    public static int[] getArrayFromInput() {
        // Get array from user input
        int[] tempArray = new int[100050];
        Scanner scanner = new Scanner(System.in);

        int totalNumber = scanner.nextInt();
        for (int i = 0; i < totalNumber; i++){
            tempArray[i] = scanner.nextInt();
        }

        scanner.close();
        return tempArray;
    }

    public static int maxIntervalArray(int[] array) {
        // Method for computing the result with O(n) complexity

        // Calculate the prefix sum of the array
        // The sum of indices (i,j] is prefixSum[j] - prefixSum[i]
        int[] prefixSum = getPrefixSum(array);
        // displayArray(prefixSum);

        // As the right index j must be greater than or equal to i,
        // we have to search for the maximum prefix sum for each
        // left index i
        int[] suffixMax = getSuffixMax(prefixSum);
        // displayArray(suffixMax);

        // Now we can calculate the maximum subarray
        int maxSubarray = 0; // In case the result is less than 0
        for (int i = 0; i < array.length; i++) {
            maxSubarray = Math.max(maxSubarray, suffixMax[i] - prefixSum[i]);
        }
        maxSubarray = Math.max(maxSubarray, prefixSum[0]); // In case the desired subarray starts from the start of the array
        
        return maxSubarray;
    }

    private static int[] getPrefixSum(int[] array) {
        // Shallow copy
        int[] prefixSum = Arrays.copyOf(array, array.length);

        for (int i = 1; i < prefixSum.length; i++) {
            prefixSum[i] += prefixSum[i-1];
        }
        return prefixSum;
    }

    private static int[] getSuffixMax(int[] array) {
        // Shallow copy
        int[] suffixMax = Arrays.copyOf(array, array.length);

        for (int i = suffixMax.length - 2; i >= 0; i--) {
            suffixMax[i] = Math.max(suffixMax[i], suffixMax[i+1]);
        }
        return suffixMax;
    }

    // Debugging use
    private static void displayArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            System.out.print(" ");            
        }
        System.out.println("");
    }
}

运行结果

输入1

6
1 -2 3 -4 5 -6

输出1

5

输入2

7
1 -9 8 5 -9 6 4

输出2

14