算法题6 最大数对差值

题目

　　题目来源:http://www.cnblogs.com/python27/archive/2011/12/01/2270724.html

　　数组中，数字减去它右边（不要求相邻）的数字得到一个数对之差。求所有数对之差的最大值。例如：数组{2, 4, 1, 16, 7, 5, 11, 9},数对之差的最大值是11，是16-5的结果。

分析

　　对于上述数组的元素9来说，它的最大数对差值等于其前面子数组中的最大值16和它的差，同理对于元素11，它的最大数对差值等于前面子数组的最大值16和它的差。

由此可以得知，求数组中的右减最大差值数对，就是求子数组最大值和右邻元素的差值，然后选取最大的那个。

算法时间复杂度O(n)

代码

 1 int MaxRightDiff(int arr[],int len)
 2 {
 3     if (arr==NULL||len<=0)
 4         throw std::exception("Invalid input.");
 5 
 6     int idx1=0,idx2=0;
 7     int max=arr[0],max_dif=0x80000000;
 8     for (int i=1;i<len;i++)
 9     {
10         int dif=max-arr[i];
11         if (dif>max_dif)
12         {
13             idx2=i;
14             max_dif=dif;
15         }
16         if (max<arr[i])
17         {
18             idx1=i;
19             max=arr[i];
20         }
21     }
22 
23     return max_dif;
24 }