详解算法最长连续子序列系列问题

常规最长连续子序列问题通常这个算法的问题主要形式主要是给定一个无序的整数数组，然后找出最长连续子序列的长度,以下代码全部基于C++语言进行演示

常规解法这种解法是正常人刚开始看到这个问题时，头脑中冒出的第一种解法，这个解法认为这个数组开始的每个数字都是一个连续数组的开头，然后从这个起点开始遍历知道剩下的数字有没有相对上一个数字连续的数字，一直迭代到不存在的某个数字，顺便记录最大的连续子序列长度。

bool isContain(int arr[],int arrLength,int num)
{
    for(int i=0;i<arrLength;i++)
    {
        if(arr[i]==num)return true;
        return false;
    }

}
int longestContinueArray(int arr[])
{
int longestStreak=0;
int arrLenth=arr.length;
for(int num:arr)
{
    int currentNum=num;
    int currentStreak=1;
   while(isContain(arr,arrLength,currentNum))
   {
       currentNum+=1;
       currentStreak+=1;
   }
   longestStreak=Math.max(longestStreak,currentStreak);
}
return longestStreak;
}

这种算法的话时间复杂度是非常糟糕的（因为一般来说刚开始解决问题时的头一个方法永远是一个最复杂的方法。。。最简单的一般都是最复杂的），因为他的时间复杂度大概为O(n^3)。所以我们现在考虑如何优化这个算法，首先因为我们要找的是个连续序列，所以可以先进行排序和去重，这样子可以省掉n个时间复杂度的查找时间；然后我们必须考虑程序中提供的数组是不是为空，如果为空或者为null的话我们应该考虑以下如何处理这种错误情况；最后我们发现我们在遍历过程中出现了大量的重复过程比如：

1,2,7,3,4,5

比如上面这个数组的最长连续子序列肯定是5，然后我们根据上面那个算法可以发现，当for循环中的num为1时，能够查到的最长序列为5，当num为2时，我们发现我们的现在查到的以前已经查过了，想办法不查这一部分可以大大优化整个算法的时间复杂度：

int longestContinueArray(int []arr)
{
    if(arr==null||arr.length==0)return 0;
    Array.sort(arr);
    int longestStreak=1;
    int currentStreak=1;
    for(int i=1;i<arr.length;i++)
    {
       if(i+1<arr.length&&arr[i]+1==arr[i+1])
       currentStreak++;
       else
       {
           longestStreak=Math.max(longestStreak,currentStreak);
           currentStreak=1;
       }
    }
    return longestStreak;
}

以上代码解决了以上的问题，但是时间复杂度最优为nlogn, 最差为n^2,其实我们完全可以用c++一些提供的特定结构来进一步简化整体算法的时间复杂度。比如我们可以使用C++中的set，自动去重且查询为O(1)

int longestContinueArray(int arr[])
{
    set<int>numSet=new set<int>();
    for(int num:arr)numSet.add(num);
    int longestStreak=0;
    for(int num:numSet)
    {
        if(!numSet.contains(num-1))
        {
            int currentNum=num;
            int currentStreak=1;
            while(numSet.contains(currentNum+1))
            {
                currentNum+=1;
                currentStreak+=1;
            }

            longestStreak=Math.max(longestStreak,currentStreak);
        }
    }
    return longestStreak;
}

2.最长连续公共子序列先占个坑，未完待续。。。。

详解算法 最长连续子序列系列问题

详解算法最长连续子序列系列问题