UVa 11078 - Open Credit System - Algorithms and Data Structures for OJ

Problem link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2019

In this problem there are some IQ test score. The first score is the score of senior most students and the last score is the score of junior most students. The problem ask to find the maximum difference of score between the senior and junior students. A straight forward solution of this problem will be iterate from i=1 to n-1 and in each iteration again iterate from j=i+1 to n calculate score[i]-score[j] and find the maximum difference. But as the maximum number of student can be 100,000 so there is a good chance to get time limit exits. So you need to find a solution which is linear time solution.

There is an important thing to understand. I am explaining this through an example bellow.

Suppose n is 10. And the score of 10 student is

100 90 80 40 65 110 50 47 38 19

Now take a variable and calculate difference between first two score.

difference = 100 – 80;

Take another variable to store the maximum value.

largeValue = max( 100, 80 );

Now as the large value between 100 and 90 is 100, so there is no need the calculate the difference between 90 and 80. We will find the difference between largeValue and 80.

Thus, temp = largeValue – 80;

difference = max( difference, temp );

largeValue = max( largeValue, 80 );

The next score is 40, large value is 100.

So temp = largeValue – 40;

difference = max( difference, temp );

largeValue = max( largeValue, 40 );

Every time you need to maintain the large value. Continue doing so you will find that the difference = 91. And that is the answer.

As the value of n is at least 2, so first find the difference between the first two score. Then iterate through i=3 to n. Find difference between largeValue and score[i]. Update difference and largeValue.