java - 如果我的 int 数组有超过 65535 个元素，为什么最大总和子数组停止工作？

Question

我有一个程序，它根据用户输入生成一个数组(数组可以是降序、升序和随机两种类型)，然后它使用暴力破解、分而治之和动态规划计算最大子数组和。在 65535 的值之前，它似乎工作正常且花花公子。之后，每个总和都不一样，这是不应该发生的。 35535 是 2 的 16 次方减 1，所以我想知道我是否达到了某个极限。当我打印数组时，它似乎打印得很好，所以我不认为问题是数组没有正确生成。

这是主类:

public class MainClass {

public static void main(String[] args) {

    int n = Integer.parseInt(args[1]);
    int[] maxsubarray1;
    maxsubarray1 = new Generator(n,args[3]).getArray();
    int[] maxsubarray2 = Arrays.copyOf(maxsubarray1,maxsubarray1.length);
    int[] maxsubarray3 = Arrays.copyOf(maxsubarray1,maxsubarray1.length); 

    System.out.println(Arrays.toString(maxsubarray1));
    solver solver = new solver();
    int solution;
    //if (args[5].equalsIgnoreCase("bruteforce")){
        long startTime = System.currentTimeMillis();
        solution = solver.bruteforce(maxsubarray1, n);
        System.out.println("__________BRUTE FORCE________\nThe sum of the array is "+solution);
        long endTime = System.currentTimeMillis() - startTime;
        System.out.println(endTime);
    //}
    //if (args[5].equalsIgnoreCase("divideconquer")){
        long startTime2 = System.currentTimeMillis();
        int solutiondivideconquer = solver.divideconquer(maxsubarray2, 0, n);
        System.out.println("__________DIVIDE AND CONQUERE________\nThe sum of the array is "+ solutiondivideconquer);
        long endTime2 = System.currentTimeMillis() - startTime2;
        System.out.println(endTime2);
    //}
    //if (args[5].equalsIgnoreCase("dynprog")){
        long startTime3 = System.currentTimeMillis();
        int solutiondynprog = solver.dynprog(maxsubarray3, n);
        System.out.println("__________DYNAMIC PROGRAMMING________\nThe sum of the array is "+ solutiondynprog);
        long endTime3 = System.currentTimeMillis() - startTime3;
        System.out.println(endTime3);
    //}
}

}

这是生成器代码:

import java.util.concurrent.ThreadLocalRandom;

public class Generator {

int size;
String type;
int[] generatedArray;

public Generator(int mysize, String mytype){
    size = mysize;
    type = mytype;
    generatedArray = new int[size];
}

public void ascending(){
    for(int i = 0; i < this.size; i++)
        generatedArray[i] = i+1;
}

public void descending(){
    for(int i = this.size -1; i >= 0; i--)
        generatedArray[i] = i+1;
}

public void random(){
    for(int i = 0; i <= this.size -1; i++)
        generatedArray[i] = ThreadLocalRandom.current().nextInt(-10*this.size, 10*this.size);
}

public void randominter(){
    for(int i = 0; i <= this.size -1; i++)
        if (i % 2 == 0)
            generatedArray[i] = ThreadLocalRandom.current().nextInt(1, 10*this.size);
        else if (i % 2 == 1)
            generatedArray[i] = ThreadLocalRandom.current().nextInt(-10*this.size, -1);
}

public int[] getArray(){
    if (type.equalsIgnoreCase("descending")){
        this.descending();
        return generatedArray;
    }
    if (type.equalsIgnoreCase("ascending")){
        this.ascending();
        return generatedArray;
    }
    if (type.equalsIgnoreCase("random")){
        this.random();
        return generatedArray;
    }
    if (type.equalsIgnoreCase("randominter")){
        this.randominter();
        return generatedArray;
    }
    return null;
}
}

这是求解器类:

public class solver {


//brute force algorithm with complexity O(n^2)
int bruteforce(int array[], int n){

    int max = Integer.MIN_VALUE;
    //We go throght all the elements of the list and we try all the
    //posible combinations with all the other elements
    for (int i = 0; i < n; i++){
        int sum = 0;
        for (int j = i; j < n ; j++){
            //we add the an element in the sum
            sum += array[j];
            //we check if the sum with the new element is greater that the value we had before
            if(sum > max){
                //if it's greater, it becomes the new value
                max = sum;
            }
        }    
    }
    //we return the maximum value we have found
    return max;
}

//to implement the divide and conquer algorithm we have to take into account the
// maximum subarray can have elements in the right subarray and in the left subarray
int maxCrossingSum(int array[], int l, int m, int h){
    int sum = 0;
    int left_sum = Integer.MIN_VALUE;
    //Has the elements on the left part of the arrray
    for ( int i = (int)m; i >= l; i--){
        sum = sum + array[i];
        if( sum > left_sum ){
            left_sum = sum;
        }
    }

    sum = 0;
    int right_sum = 0;
    //Has the elements in the right part of the array
    for ( int j = (int)m+1; j <= h; j++){
        sum = sum + array [j];
        if (sum > right_sum){
            right_sum = sum;
        }
    }
    //returns the sun of the elements on the left and the right of the array
    return left_sum + right_sum; 
}

//returns the sum of the maximum subarray
int maxSubarraySum(int array[], int l, int h){

    if(l == h)
        return array[1];

    int m = (l + h)/2;
    //checks which is the maximum between left and right
    int maxBetweenLeftRight = max(maxSubarraySum(array, l, m), maxSubarraySum(array, m+1,h));
    int crossing = maxCrossingSum(array, l, m,h-1);
    //retrns the maximum between one of the sides and the crossing sum
    return max(maxBetweenLeftRight, crossing);

}
//divide and conquere algorithm with complexity O(nlogn)
 //only made to make it more understandable from the main
//can call maxSubarraySum and it would be the same
int divideconquer (int array[], int l, int h){

    return maxSubarraySum(array, l, h);
}

//dynamic programming algorithm with complexity O(n)
int dynprog(int array[], int n){
    int a = array[0];
    int b = array[0];
    //for all the elements checks if the sum was better until the 
    //step before or adding the element
    for (int i = 1 ; i < n; i++){
        a= max (a+ array[i], array[i]);
        b= max(b, a);
    }
    return b;
}
}

将所有整数更改为长整数也无济于事。

Answer 1

我已经复制了您的代码，将所有整数更改为长整数，并且工作正常。还更改了 n = Integer.parseInt(args[0]) 而不是 n = Integer.parseInt(args[1])。
然后我将我的程序命名为 program_name 1000 random。

我已经在 excel 中检查过，只有 bruteforce 是错误的。我已将 Integer.MIN_VALUE 更改为 Long.MIN_VALUE。并且 int sum 到 long sum。

主.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;


public class Main {

    public static void main(String[] args) {

        int n = Integer.parseInt(args[0]);
        long[] maxsubarray1;
        maxsubarray1 = new Generator(n, args[1]).getArray();
        long[] maxsubarray2 = Arrays.copyOf(maxsubarray1, maxsubarray1.length);
        long[] maxsubarray3 = Arrays.copyOf(maxsubarray1, maxsubarray1.length);

        System.out.println(Arrays.toString(maxsubarray1));
        solver solver = new solver();
        long solution;
        //if (args[5].equalsIgnoreCase("bruteforce")){
        long startTime = System.currentTimeMillis();
        solution = solver.bruteforce(maxsubarray1, n);
        System.out.println("__________BRUTE FORCE________\nThe sum of the array is " + solution);
        long endTime = System.currentTimeMillis() - startTime;
        System.out.println(endTime);
        //}
        //if (args[5].equalsIgnoreCase("divideconquer")){
        long startTime2 = System.currentTimeMillis();
        long solutiondivideconquer = solver.divideconquer(maxsubarray2, 0, n);
        System.out.println("__________DIVIDE AND CONQUERE________\nThe sum of the array is " + solutiondivideconquer);
        long endTime2 = System.currentTimeMillis() - startTime2;
        System.out.println(endTime2);
        //}
        //if (args[5].equalsIgnoreCase("dynprog")){
        long startTime3 = System.currentTimeMillis();
        long solutiondynprog = solver.dynprog(maxsubarray3, n);
        System.out.println("__________DYNAMIC PROGRAMMING________\nThe sum of the array is " + solutiondynprog);
        long endTime3 = System.currentTimeMillis() - startTime3;
        System.out.println(endTime3);
        //}
    }

}

求解器.java

public class solver {


    //brute force algorithm with complexity O(n^2)
    long bruteforce(long array[], int n){

        long max = Long.MIN_VALUE;
        //We go throght all the elements of the list and we try all the
        //posible combinations with all the other elements
        for (int i = 0; i < n; i++){
            long sum = 0;
            for (int j = i; j < n ; j++){
                //we add the an element in the sum
                sum += array[j];
                //we check if the sum with the new element is greater that the value we had before
                if(sum > max){
                    //if it's greater, it becomes the new value
                    max = sum;
                }
            }
        }
        //we return the maximum value we have found
        return max;
    }

    //to implement the divide and conquer algorithm we have to take into account the
// maximum subarray can have elements in the right subarray and in the left subarray
    long maxCrossingSum(long array[], long l, long m, long h){
        long sum = 0;
        long left_sum = Integer.MIN_VALUE;
        //Has the elements on the left part of the arrray
        for ( int i = (int)m; i >= l; i--){
            sum = sum + array[i];
            if( sum > left_sum ){
                left_sum = sum;
            }
        }

        sum = 0;
        long right_sum = 0;
        //Has the elements in the right part of the array
        for ( int j = (int)m+1; j <= h; j++){
            sum = sum + array [j];
            if (sum > right_sum){
                right_sum = sum;
            }
        }
        //returns the sun of the elements on the left and the right of the array
        return left_sum + right_sum;
    }

    //returns the sum of the maximum subarray
    long maxSubarraySum(long array[], long l, long h){

        if(l == h)
            return array[1];

        long m = (l + h)/2;
        //checks which is the maximum between left and right
        long maxBetweenLeftRight = max(maxSubarraySum(array, l, m), maxSubarraySum(array, m+1,h));
        long crossing = maxCrossingSum(array, l, m,h-1);
        //retrns the maximum between one of the sides and the crossing sum
        return max(maxBetweenLeftRight, crossing);

    }
    //divide and conquere algorithm with complexity O(nlogn)
    //only made to make it more understandable from the main
//can call maxSubarraySum and it would be the same
    long divideconquer (long array[], int l, int h){

        return maxSubarraySum(array, l, h);
    }

    //dynamic programming algorithm with complexity O(n)
    long dynprog(long array[], int n){
        long a = array[0];
        long b = array[0];
        //for all the elements checks if the sum was better until the
        //step before or adding the element
        for (int i = 1 ; i < n; i++){
            a= max (a+ array[i], array[i]);
            b= max(b, a);
        }
        return b;
    }

    private long max(long a, long b) {
        if (a > b ) return a;
        else return b;
    }
}

生成器.java

import java.util.concurrent.ThreadLocalRandom;

public class Generator {

    int size;
    String type;
    long[] generatedArray;

    public Generator(int mysize, String mytype) {
        size = mysize;
        type = mytype;
        generatedArray = new long[size];
    }

    public void ascending() {
        for (int i = 0; i < this.size; i++)
            generatedArray[i] = i + 1;
    }

    public void descending() {
        for (int i = this.size - 1; i >= 0; i--)
            generatedArray[i] = i + 1;
    }

    public void random() {
        for (int i = 0; i <= this.size - 1; i++)
            generatedArray[i] = ThreadLocalRandom.current().nextInt(-10 * this.size, 10 * this.size);
    }

    public void randominter() {
        for (int i = 0; i <= this.size - 1; i++)
            if (i % 2 == 0)
                generatedArray[i] = ThreadLocalRandom.current().nextInt(1, 10 * this.size);
            else if (i % 2 == 1)
                generatedArray[i] = ThreadLocalRandom.current().nextInt(-10 * this.size, -1);
    }

    public long[] getArray() {
        if (type.equalsIgnoreCase("descending")) {
            this.descending();
            return generatedArray;
        }
        if (type.equalsIgnoreCase("ascending")) {
            this.ascending();
            return generatedArray;
        }
        if (type.equalsIgnoreCase("random")) {
            this.random();
            return generatedArray;
        }
        if (type.equalsIgnoreCase("randominter")) {
            this.randominter();
            return generatedArray;
        }
        return null;
    }
}