首页 > 代码库 > 57. 数对之差的最大值:4种方法详解与总结[maximum difference of array]

57. 数对之差的最大值:4种方法详解与总结[maximum difference of array]

【本文链接】

http://www.cnblogs.com/hellogiser/p/maximum-difference-of-array.html

题目】

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

分析

看到这个题目,很多人的第一反应是找到这个数组的最大值和最小值,然后觉得最大值减去最小值就是最终的结果。这种思路忽略了题目中很重要的一点:数对之差是一个数字减去它右边的数字(不包括自身)。由于我们无法保证最大值一定位于数组的左边,因此这个思路不管用。

有如下4种方法对此题进行解答。


 【方法1:蛮力法

很容易想到,让每一个数字逐个减去它右边的所有数字,并通过比较得到数对之差的最大值。所有的数对只差共有n*(n-1)/2,因而时间复杂度为O(n^2)。我们设定只有1个数字时,最大数对之差为INT_MIN,即0x80000000。

【代码】

 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
// 57_MaxDiffOfArray.cpp : Defines the entry point for the console application.
//

/*
     version: 1.0
     author: hellogiser
     blog: http://www.cnblogs.com/hellogiser
     date: 2014/5/24
*/


#include "stdafx.h"
#include <iostream>
using namespace std;

// brute force
int MaxDiff_BruteForce(int *numbers, int length)
{
    
// O(n^2)
    if(NULL == numbers || length < 2)
        
return INT_MIN;
    
//init maxdiff to min value
    int maxDiff = INT_MIN;
    
for (int i = 0; i < length; ++i)
     {
        
for (int j = i + 1; j < length; ++j)
         {
            
int diff = numbers[i] - numbers[j];
            
// update maxDiff
            if (diff > maxDiff)
                 maxDiff = diff;
         }
     }
    
return maxDiff;
}

void test_base(int *numbers, int length)
{
     cout << MaxDiff_BruteForce(numbers, length) << endl;
}


void test_case1()
{
    
int a[] = {2};
    
int length = sizeof(a) / sizeof(int);
     test_base(a, length);
}

void test_case2()
{
    
int a[] = {24};
    
int length = sizeof(a) / sizeof(int);
     test_base(a, length);
}

void test_case3()
{
    
int a[] = {2411675119};
    
int length = sizeof(a) / sizeof(int);
     test_base(a, length);
}

void test_main()
{
     test_case1();
     test_case2();
     test_case3();
}

int _tmain(int argc, _TCHAR *argv[])
{
     test_main();
    
return 0;
}
/*
-2147483648
-2
11
*/

方法2:分治法

通常【蛮力法】不会是最好的解法,我们想办法减少减法的次数。

假设我们把数组以中间元素为分割点分成两个子数组,我们其实没有必要拿左边的子数组中较小的数字A去和右边的子数组中较大的数字B作减法。我们可以想象,数对之差的最大值只有可能是下面三种情况之一:

(1)A和B都在第一个子数组中,即第一个子数组中的数对之差的最大值;

(2)A和B都在第二个子数组中,即第二个子数组中数对之差的最大值;

(3)A在第一个子数组中,是第一个子数组的最大值;B在第二个子数组中,是第二个子数组的最小值。

那么这三个差值的最大者就是整个数组中数对之差的最大值。

在前面提到的三种情况中,得到第一个子数组的最大值和第二子数组的最小值不是一件难事,但如何得到两个子数组中的数对之差的最大值?这其实是原始问题的子问题,我们可以递归地解决。

【代码】

 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
/*
     version: 1.0
     author: hellogiser
     blog: http://www.cnblogs.com/hellogiser
     date: 2014/5/24
*/


#define MIN(a,b) a<b?a:b
#define MAX(a,b) a>b?a:b

// get max of a b c
int max3(int a, int b, int c)
{
    
int t = a > b ? a : b;
    
return t > c ? t : c;
}

// get max diff from [left,right] and pass out max/min value
int MaxDiffCore(int *left, int *right, int *min, int *max)
{
    
if(left == right)
     {
         *max = *min = *left;
        
return INT_MIN;
     }
    
int *middle = left + (right - left) / 2;
    
// get left max diff
    int minLeft, maxLeft;
    
int leftDiff = MaxDiffCore(left, middle, &minLeft, &maxLeft);

    
// get right max diff
    int minRight, maxRight;
    
int rightDiff = MaxDiffCore(middle + 1, right, &minRight, &maxRight);

    
// get cross max diff
    int crossDiff = maxLeft - minRight;

    
// update whole array min and max value
    *min = MIN(minLeft, minRight);
     *max = MAX(maxLeft, maxRight);

    
int maxDiff = max3(leftDiff, rightDiff, crossDiff);
    
return maxDiff;
}

// divide and conquer
int MaxDiff_DivideAndConquer(int *numbers, int length)
{
    
// T(n)=2*T(n/2)+O(1)===>Tn=O(n)
    if(NULL == numbers || length < 2)
        
return INT_MIN;
    
int min, max;
    
return MaxDiffCore(numbers, numbers + length - 1, &min, &max);
}

在函数MaxDiffCore中,我们先得到第一个子数组中的最大的数对之差leftDiff,再得到第二个子数组中的最大数对之差rightDiff。接下来用第一个子数组的最大值减去第二个子数组的最小值得到crossDiff。这三者的最大值就是整个数组的最大数对之差。在求解数对之差的同时,还要求解子数组的最小值和最大值。


 【方法3:转化法

转换为求子数组的最大和问题。

接下来再介绍一种比较巧妙的解法。如果输入一个长度为n的数组numbers,我们先构建一个长度为n-1的辅助数组diff,并且diff[i]等于numbers[i]-numbers[i+1](0<=i<n-1)。如果我们从数组diff中的第i个数字一直累加到第j个数字(j > i),也就是diff[i] + diff[i+1] + … + diff[j] = (numbers[i]-numbers[i+1]) + (numbers[i + 1]-numbers[i+2]) + ... + (numbers[j] – numbers[j + 1]) = numbers[i] – numbers[j + 1]。

分析到这里,我们发现原始数组中最大的数对之差(即numbers[i] – numbers[j + 1])其实是辅助数组diff中最大的连续子数组之和。

【代码】

 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
/*
     version: 1.0
     author: hellogiser
     blog: http://www.cnblogs.com/hellogiser
     date: 2014/5/24
*/

// max sub sequence sum
int MaxSubSequenceSum(int *array, int length)
{
    
// f = max(f+a[i],a[i])
    if(NULL == array || length <= 0)
        
return INT_MIN;

    
int f = array[0];
    
int greatest = array[0];
    
for (int i = 1; i < length; i++)
     {
        
if (f <= 0)
             f = array[i];
        
else
             f += array[i];
        
// update greatest
        if (greatest < f)
             greatest = f;
     }
    
return greatest;
}

// maximum continuous sub-sequence sum
int MaxDiff_Transformation(int *numbers, int length)
{
    
// Tn=O(n)
    if(NULL == numbers || length < 2)
        
return INT_MIN;
    
// generate diff array
    int diffLength = length - 1;
    
int *diff = new int[diffLength];
    
for (int i = 0; i < diffLength; ++i)
         diff[i] = numbers[i] - numbers[i + 
1];

    
// get maximum continuous sub-sequence sum
    int maxDiff = MaxSubSequenceSum(diff, diffLength);
    
delete []diff;
    
return maxDiff;
}

方法4:动态规划法

既然我们可以把求最大的数对之差转换成求子数组的最大和,而子数组的最大和可以通过动态规划求解,那我们是不是可以通过动态规划直接求解呢?下面我们试着用动态规划法直接求数对之差的最大值。

我们定义diff[i]是以数组中第i个数字为减数的所有数对之差的最大值(0<=i<n)。

则有diff[i+1] = max(diff[i], maxi-array[i+1]),maxi表示数组array[0,…i]的最大值。

【代码】

 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
/*
     version: 1.0
     author: hellogiser
     blog: http://www.cnblogs.com/hellogiser
     date: 2014/5/24
*/


// max diff using dynamic programming
// diff[i]: maxDiff ending at array[i] (0<=i<n)
// maxi: max value of array[0,...i]
// diff[i+1] = max (diff[i],maxi-array[i+1])
int MaxDiff_DP(int *numbers, int length)
{
    
// Tn=O(n)
    if(NULL == numbers || length < 2)
        
return INT_MIN;
    
int maxi = numbers[0];
    
int maxDiff = INT_MIN;
    
for (int i = 1; i < length; i++)
     {
        
if(maxi < numbers[i - 1])
             maxi = numbers[i - 
1];

        
if(maxDiff < maxi - numbers[i])
             maxDiff = maxi - numbers[i];
     }
    
return maxDiff;
}

【总结】

方法1:蛮力法】时间复杂度为O(n2),空间复杂度为O(1)。

方法2:分治法】时间复杂度为O(n),空间复杂度为O(1)。 由于该方法基于递归实现,因此会有额外的时间、空间消耗。

方法3:转化法】时间复杂度为O(n),空间复杂度为O(n)。

方法4:动态规划法】时间复杂度为O(n),空间复杂度为O(1)。该方法则没有额外的时间、空间消耗,并且它的代码是最简洁的,因此这是最值得推荐的一种解法。

【参考】

http://zhedahht.blog.163.com/blog/static/2541117420116135376632/

http://www.cnblogs.com/python27/archive/2011/12/01/2270724.html

【本文链接】

http://www.cnblogs.com/hellogiser/p/maximum-difference-of-array.html