Подсчет инверсий для массива из 100 000 целых чисел, зачем получить отрицательный результат?

Question

import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.Scanner; 


public class InversionCounter { 
    public static void main(String[] args) { 
     Scanner scanner = null; 
     try { 
      scanner = new Scanner(new File("src/IntegerArray.txt")); 
     } catch (FileNotFoundException e) { 
      // TODO Auto-generated catch block 
      e.printStackTrace(); 
     } 
     int [] nums = new int [100000]; 
     int i = 0; 
     while(scanner.hasNextInt()){ 
      nums[i++] = scanner.nextInt(); 
     } 
     System.out.println(countInversions(nums)); 

    } 

public static int countInversions(int[] nums) { 
    int count = 0; 
    for (int i=0;i<nums.length-1;i++) { 
     for (int j=i+1;j<nums.length;j++) { 
      if (nums[i]>nums[j]) { 
       count++; 
      } 
      else {continue;} 
     } 
    } 
    return count; 
} 

} 

Приведенный выше код считывает 100 000 целых чисел из файла и подсчитывает инверсии для этого массива целых чисел. Выход, вероятно, очень большой, например, 1198233847 и определенно должен быть положительным. Однако он выдает отрицательный результат, например -1887062008. Логика программы, вероятно, будет правильной, поскольку я попытался использовать другие алгоритмы с той же целью и получил такое же отрицательное число, как и вывод. Я подозреваю, что результат слишком велик, и в результате Java превращает его в отрицательный.

Answer 1

Максимальное значение int - 2,147,483,647 - то, что вы видите, переполнено. Вы должны сделать count a long, если вы ожидаете, что он будет таким большим.

источник: http://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html

Answer 2

Наихудший здесь 4,999,950,000 инверсий, которая больше, чем максимальное значение INT в (2147483647). Вероятно, вы должны использовать длинный номер для хранения.