算法题——数组内有序对的最大距离

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int maxDist(int num[], int n)
 6 {
 7     if(n < 2)
 8         return 0;
 9 
10     vector<int> left_min_pos(n, 0);
11     int cur_min_pos = 0;
12     int max_dist = 0;
13 
14     for(int i = 1; i < n; ++i)
15     {
16         if(num[i] < num[cur_min_pos])
17         {
18             left_min_pos[i] = i;
19             cur_min_pos = i;
20         }
21         else
22         {
23             left_min_pos[i] = cur_min_pos;
24         }
25     }
26 
27     for(int i = n - 1, j = n - 1; i >= 0; )　　//i < j
28     {
29         i = left_min_pos[i];
30         
31         if(num[j] >= num[i])    //找到一个有序对，或是同一个元素
32         {
33             if(j - i > max_dist) 
34             {
35                 max_dist = j - i;
36             }
37             --i;            //对于当前的i来说，j已是最远的，所以固定住j，i往左走，找到更大的j-i
38         }
39         else
40         {
41             --j;            //不是有序对，对于j来说，上一个i已是最远的，固定住i，j往左走
42         }
43     }
44 
45     return max_dist;
46 }
47 
48 int main()
49 {
50     const int n = 5;
51     int num[n] = {3, 6, 4, 1, 2};
52 
53     cout << maxDist(num, n) << endl;
54 
55     return 0;
56 }