用DP乱写了点code,发现还是得O(n2),不好意思,刚刚想歪了。
typedef struct subarray_info
{
int start;
int end;
int min;
int max;
int new_start;
}subarray_info;
void calculate_subarray_info (subarray_info * info, int input_array[], int n
, int k)
{
if ( n == 1)
{
info[0].start = 0;
info[0].end = 0;
info[0].min = input_array[0];
info[0].max = input_array[0];
info[0].new_start = 0;
return;
}
calculate_subarray_info (info, input_array, n-1, k);
subarray_info tmp_info = info[n-2];
if ( tmp_info.start == tmp_info.new_start)
{
//currently the solution is from start all the way to the end
if ( (tmp_info.max - input_array[n-1]) <= k && (input_array[n-1] -
tmp_info.min) <= k)
{
//and the soluton continue grow
info[n-1].start = tmp_info.start;
info[n-1].end = n-1;
info[n-1].min = (input_array[n-1] < tmp_info.min)? input_array[n
-1] :tmp_info.min;
info[n-1].max = (input_array[n-1]> tmp_info.max)? input_array[n-
1] :tmp_info.max;
info[n-1].new_start = tmp_info.new_start;
return;
}
else
{
//now the solution break, calculate all the way back for the new
solution start from end
int tmp_max, tmp_min;
tmp_max = input_array[n-1];
tmp_min = input_array[n-1];
int tmp_new_start = n -1;
for (int i = n -2; i >tmp_info.start; i--)
{
if ((tmp_max - input_array[i]) > k || (input_array[i] - tmp_
min ) > k)
{
tmp_new_start = i + 1;
break;
}
tmp_max = (input_array[i]>tmp_max)? input_array[i]:tmp_max;
tmp_min = (input_array[i]}
//something went wrong here.throw a exception
info[n-1].start = tmp_info.start;
info[n-1].end = tmp_info.end;
info[n-1].min = tmp_min;
info[n-1].max = tmp_max;
info[n-1].new_start = tmp_new_start;
return;
}
}
else
{
//current best solution is a subarray in the middle and can not grow
anymore
if ( (tmp_info.max - input_array[n-1]) <= k && (input_array[n-1] -
tmp_info.min) <= k)
{
//and the new soluton continue grow, compare the new solution's
lenght with the old one
if ( (n-1 - tmp_info.new_start) > (tmp_info.end - tmp_info.start
))
{
//the new solution is the longer one, update it
info[n-1].start = tmp_info.new_start;
info[n-1].end = n-1;
info[n-1].min = (input_array[n-1] < tmp_info.min)? input_
array[n-1] :tmp_info.min;
info[n-1].max = (input_array[n-1]> tmp_info.max)? input_
array[n-1] :tmp_info.max;
info[n-1].new_start = tmp_info.new_start;
return;
}
else
{
//still the old solution is the best solution so far
info[n-1].start = tmp_info.start;
info[n-1].end = tmp_info.end;
info[n-1].min = (input_array[n-1] < tmp_info.min)? input_
array[n-1] :tmp_info.min;
info[n-1].max = (input_array[n-1]> tmp_info.max)? input_
array[n-1] :tmp_info.max;
info[n-1].new_start = tmp_info.new_start;
return;
}
}
else
{
//now the new solution break, calculate all the way back for the
new solution start from end
int tmp_max, tmp_min;
tmp_max = input_array[n-1];
tmp_min = input_array[n-1];
int tmp_new_start = n -1;
for (int i = n -2; i >tmp_info.new_start; i--)
{
if ((tmp_max - input_array[i]) > k || (input_array[i] - tmp_
min ) > k)
{
tmp_new_start = i+1;
break;
}
tmp_max = (input_array[i]>tmp_max)? input_array[i]:tmp_max;
tmp_min = (input_array[i]}
info[n-1].start = tmp_info.start;
info[n-1].end = tmp_info.end;
info[n-1].min = tmp_min;
info[n-1].max = tmp_max;
info[n-1].new_start = tmp_new_start;
return;
}
}
}
//maximum length subarray such that maximum difference is less than k
//gonna solve this problem using dynamical programming
int get_max_len_subarray_with_maxdiff ( int input_array [] , int n, int k)
{
///remember veirfy the input: input_array, n, k
subarray_info * info = new subarray_info[n];
calculate_subarray_info (info, input_array, n, k);
int max_len = info[0].end - info[0].start + 1;
for (int i = 0; i < n; i++)
{
int new_len = info[i].end - info[i].start + 1;
if (new_len > max_len)
max_len = new_len;
}
return max_len;
}
void test_get_max_subarray (void)
{
int a [] = { 1, 2, 3, 4, 6, 11, 14, 33, 28, 29, 30, 31, 32, 28, 28, 29,
30, 1, 2, 3};
int result = get_max_len_subarray_with_maxdiff ( a , 20, 10);
printf ("result %d\n",result);
}