Блин, несколько часов убил на задачку. Потом решил таки проверить с использованием «длинной арифметики», так сказать, в лоб и посмотреть сколько времени выполняется.
тестировал на java с использованием BigInteger
заполнение и вычисление:
Random r = new Random();
Vector< Vector<Integer> > nums = new Vector<Vector<Integer>>();
long t = System.currentTimeMillis();
System.out.println( "Starting generate example" );
for( int column = 0; column < 20 ; column++ ){
Vector<Integer> rows = new Vector<Integer>();
for( int row = 0; row < 1000; row++ ){
rows.add( r.nextInt() );
}
nums.add(rows);
}
long t2 = System.currentTimeMillis();
System.out.println( "generate example finished at " + ( t2 - t ) );
System.out.println( "Starting getAnswer" );
System.out.println( p.getAnswer2(nums) );
long t3 = System.currentTimeMillis();
System.out.println( "getAnswer finished at " + ( t3 - t2) );
getAnswer2 — банальное умножение в цикле и нахождение максимального результата.
вывод:
Starting generate example
generate example finished at 24
Starting getAnswer
13
getAnswer finished at 385
Время в милисикундах, на максимальных условиях, а 0,018 возможно была матрица не 20х1000?
