【本文鏈接】
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[] = {2, 4};
int length = sizeof(a) / sizeof(int);
test_base(a, length);
}
void test_case3()
{
int a[] = {2, 4, 1, 16, 7, 5, 11, 9};
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
