微软面试100题(94):求有序数组中公差为d的最长等差数列

原题目是求一个无序数组中最长的等差数列。

求随机数构成的数组中找到长度大于=3 的最长的等差数列, 输出等差数列由小到大:
如果没有符合条件的就输出
格式：
输入[1,3,0,5,-1,6]
输出[-1,1,3,5]

 

 

解法如下：

1.排序

2.设极值分别为min, max,那么公差范围为(1..max-min);

3.公差d从(1..max-min)循环，求出每次的最长的数列长度f(d)

<根据已得到的数列的长度，还可以进一步减少循环次数>

 

所以该题目基础是求出一个有序数组中公差为d的最长等差数列。

 

较简单动态规划:

设等差数列的起始下标为s,当前下标为i，从s到i，构成的最长的等差数列长度为f(s,i),有

  f(s,i+1) = f(s,i) +1 ( input[i+1] == input[s] + f(s,i)*d)

             f(s,i)    ( input[i+1] != input[s] + f(s,i)*d)

 

最长的数列长度为：

    maxLen = max{f(s,i) s∈[1 ..  max-min] i∈[0,sizeof(input)) }

 

算法时间复杂度应为n的平方，空间复杂度可优化至O(1) （代码中为O(n)）

 

代码如下：

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000

void GetSeq(int *input, int size, int d){
    if(input == NULL) return;
    int result[MAX] = {0};

    int startIndex = 0;
    int maxLen = 0;
    int maxLenStartIndex = -1;
    for(;startIndex < size-maxLen; startIndex++){
        int i = startIndex;
        result[i] = 1;
        i++;
        for(;i<size;i++){
            result[i] = result[i-1];
            if(input[i] == input[startIndex] +result[i-1]*d){
                result[i]++;
                if(result[i]> maxLen){
                    maxLen = result[i];
                    maxLenStartIndex = startIndex;
                }
            }
            else if(input[i] > input[startIndex] + result[i-1]*d)
                break;
        }
        }
    printf("Max sequence start index: %d, length: %d \n", maxLenStartIndex, maxLen);
}

int main(){
    int input[] = {1,3,4,6,7,9,10,12,13,15,16,18,21,24};
    GetSeq(input, sizeof(input)/sizeof(int), 3);
}