数组中元素差的最大值

这道题是2016美团面试题：

1.给定一个数组arr，数组长度为len，求满足 0 <= a <= b < len的 arr[b] - arr[a]最大值。

你的想法：让每一个数字减去它右边的数字，并通过比较得到数对的最大值，时间复杂度（O^2）,这应该是面试官不想要的。

解法一：分治法(递归实现)

假设把数组分成两个子数组，用左数组最大的减去右数组最小的，最大值有三种情况：

　　(1)被减数和减数都在第一个子数组中，即第一个子数组中的数对之差的最大值；

　　(2)被减数和减数都在第二个子数组中，即第二个子数组中数对之差的最大值；

　　(3)被减数在第一个子数组中，是第一个子数组的最大值；减数在第二个子数组中，是第二个子数组的最小值。

（1）、（2）、（3）中，这三个差值的最大者就是整个数组中数对之差的最大值。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 // 解法1： 分治法（递归实现）
 5 int Max_Find(int *s,int *e,int *max,int *min)
 6 {
 7     if(s >= e)
 8     {
 9         *max = *min = *s;
10         return -1;
11     }
12     int *mid = s+(e-s)/2;
13 
14     int maxleft,minleft;
15     int left = Max_Find(s,mid,&maxleft,&minleft);
16 
17     int maxright,minright;
18     int right = Max_Find(mid+1,e,&maxright,&minright);
19 
20     int sum = maxleft - minright;
21 
22     *max = (maxleft > maxright) ? maxleft:maxright;
23     *min = (minleft < minright) ? minleft:minright;
24 
25     int m = (left > right) ? left:right;
26 
27     m = (m > sum)?m:sum;
28 
29     return m;
30 }
31 int MaxDiff(int array[], unsigned int len)
32 {
33     if(NULL == array || len < 2){
34         return -1;
35     }
36     int max, min;
37     int MaxDiff_Num = Max_Find(array, array+len-1, &max, &min);
38     printf("maxDiff_Num: %d\n\n", MaxDiff_Num);
39 }
40 
41 int main()
42 {
43     int a[2] = {10,5};
44     MaxDiff(a,2);
45 }

View Code

解法二：转化为求数字数组最大和问题。

参考：这里

使用一个辅助数组arr2，则arr2[i] = arr[i] - arr[i+1]

即：arr2中从i加到j，arr2[i] + arr2[i+1]+.....+arr2[j]

则：(arr[i]-arr[i+1])+(arr[i+1]-arr[i+2])+....(arr[j]-arr[j+1])

转化为arr[i]-arr[j+1]

 1 #include <iostream>
 2 #include <stack>
 3 #include <algorithm>
 4 #include <stdio.h>
 5 #include <string.h>
 6 #include <stdlib.h>
 7 using namespace std;
 8 int max_find(int arr[],int len)
 9 {
10     if(arr == NULL || len < 2)
11     {
12         return -1;
13     }
14     int *arr2 = new int[len - 1];
15     int i = 0;
16     for(i = 0;i < len-1;++i)
17     {
18         arr2[i] = arr[i] - arr[i+1];
19     }
20     int curS = 0;
21     int max = -1;
22     for(i = 0;i < len-1;++i)
23     {
24         if(curS <= 0)
25         {
26             curS = arr2[i];
27         }else
28         {
29             curS +=arr2[i];
30         }
31         if(curS > max)
32         {
33             max = curS;
34         }
35     }
36     if(arr2)
37     {
38         delete [] arr2;
39         arr2 = NULL;
40     }
41     printf("%d",max);
42 }
43 int main()
44 {
45     int a[2] = {10,5};
46     max_find(a,2);
47 }

View Code

解法三：动态规划法

依次遍历数组用arr[i-1]之前的最大值减去右边的元素

 1 #include <iostream>
 2 #include <stack>
 3 #include <algorithm>
 4 #include <stdio.h>
 5 #include <string.h>
 6 #include <stdlib.h>
 7 using namespace std;
 8 int max_find(int arr[],int len)
 9 {
10     if(arr == NULL || len < 2)
11     {
12         return -1;
13     }
14     int max = arr[0];
15     int sum = max - arr[1];//初始化数对差
16     int i = 0;
17     for(i = 2;i < len;++i)
18     {
19         if(arr[i-1] > max)
20         {
21             max = arr[i-1]; //左侧最大值
22         }
23         int cur = max - arr[i];//用最大的值减右侧的最小值
24         if(cur > sum) //判断是否是最大数对之差
25         {
26             sum = cur;
27         }
28     }
29     printf("%d",sum);
30 }
31 int main()
32 {
33     int a[2] = {10,5};
34     max_find(a,2);
35 }

View Code

以上三种都是O(n),那么：

第一种：递归，有递归栈

第二种：要n-1辅助数组

第三种：推荐

数组中元素差的最大值

推荐阅读