I have a problem. I have a large number of intergers in a file. After that, i have an even larger number of paris. The number of pairs are almost the square of the number of integers. And the pairs are between 0 and whatever number of integers there are
-1.
for example the file might contain: INTS: 4 7 8 49 2 30 1...
PAIRS: (0, 3) (4,5) (1,2) (0,2)...
So when (0,3) is read it will find the largest number between positions 0 and 3 of the integers and return the index (in this case 3). The pairs have to be read in sequence but the integers will probably be in an array.
Does this program require the use of dynamic programming to get the fastest possible algorithm? If so i was thinking of using a 2d array to store the answer to the first pair in the array, then fill in the rest of the array using this answer and use the array to obtain the answers.
(The array will be made up of all the ints going vertically and horizontally representing all the possible pairs. And only half of the array is required because you cant have a pair where the first number is larger than the second).
Does anyone have a better (faster) algorithm??
