題目:
題目：在數(shù)組中，數(shù)字減去它右邊的數(shù)字得到一個(gè)數(shù)對(duì)之差。求所有數(shù)對(duì)之差的最大值。例如在數(shù)組{2, 4, 1, 16, 7, 5, 11, 9}中，數(shù)對(duì)之差的最大值是11，是16減去5的結(jié)果。
對(duì)于分治算法，實(shí)現(xiàn)的不好，參考原作者的思路，對(duì)于左半部分最大值、右半部分最小值都是可以在遞歸里求出的，參考：
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<limits.h>
#define MAX(a, b) ((a)>(b) ? (a) : (b))
#define MIN(a, b) ((a)<(b) ? (a) : (b))
/*
* 題目:
* 在數(shù)組中，數(shù)字減去它右邊的數(shù)字得到一個(gè)數(shù)對(duì)之差。求所有數(shù)對(duì)之差的最大值
* 例如:
* 在數(shù)組{2, 4, 1, 16, 7, 5, 11, 9}中，數(shù)對(duì)之差的最大值是11，是16減去5的結(jié)果
*/
int
naive_solution(int *array, int len) //O(n^2)
{
int i, j, ret = INT_MIN;
for(i=0; i<len; ++i)
for(j=i+1; j<len; ++j)
ret = MAX(ret, array[i]-array[j]);
return ret;
}
int
divide_and_conquer_solution(int *array, int begin, int end) //O(nlogn)
{
if(begin >= end)
return INT_MIN;
int i, ret, left_ret, right_ret, left_max, right_min, mid;
mid = begin + ((end-begin)>>1);
left_ret = divide_and_conquer_solution(array, begin, mid);
right_ret = divide_and_conquer_solution(array, mid+1, end);
left_max = array[begin];
for(i=begin+1; i<=mid; ++i)
left_max = MAX(left_max, array[i]);
right_min = array[end];
for(i=end-1; i>mid; --i)
right_min = MIN(right_min, array[i]);
ret = MAX(left_ret, right_ret);
ret = MAX(ret, left_max-right_min);
return ret;
}
int
dynamic_programming_solution(int *array, int len) //O(n)
{
int i, cur_ret, cur_min;
cur_ret = array[len-2] - array[len-1];
cur_min = MIN(array[len-2], array[len-1]);
for(i=len-3; i>=0; --i) {
cur_ret = MAX(cur_ret, array[i]-cur_min);
cur_min = MIN(cur_min, array[i]);
}
return cur_ret;
}
int
main(int argc, char **argv)
{
int i, num, *data = NULL;
scanf("%d", &num);
assert(num>=2);
data = (int *)malloc(sizeof(int) * num);
assert(data != NULL);
for(i=0; i<num; i++)
scanf("%d", data+i);
printf("naive_solution result: %d\n", naive_solution(data, num));
printf("divide_and_conquer_solution result: %d\n", divide_and_conquer_solution(data, 0, num-1));
printf("dynamic_programming_solution result: %d\n", dynamic_programming_solution(data, num));
free(data);
return 0;
}