首页 > 代码库 > 算法-最长子序列和C/C++实现(三个复杂度)
算法-最长子序列和C/C++实现(三个复杂度)
最长子序列和的问题很简单:
就是一个数组,求出其中其中连续的某一段和,而这一段和是所有的连续段和的最大的值。求出这个值。
先说复杂度最高的:O(n3)
直接上代码,很简单的:
// // main.cpp // SumSequence // // Created by Alps on 14-7-23. // Copyright (c) 2014年 chen. All rights reserved. // #include <iostream> using namespace std; int MaxSubsequenceSum(const int A[], int N){ int ThisSum, MaxSum, i, j, k; MaxSum = 0; for(i = 0; i < N; i++){ for(j = i; j < N; j++){ ThisSum = 0; for (k = i; k < j; k++) { ThisSum += A[k]; } MaxSum = ThisSum > MaxSum ? ThisSum: MaxSum; } } return MaxSum; } int main(int argc, const char * argv[]) { int A[] = {1, 2, -5, 2, 5, 1, 8, -4}; int N = sizeof(A)/sizeof(int); // printf("%d\n",N); int MaxSum = MaxSubsequenceSum(A, N); printf("%d\n",MaxSum); return 0; }
这个其实很简单,第一层for循环是i从头开始遍历。第二层for是j从i遍历到尾。第三层就是算i到j的这一段的和。
时间复杂度是O(n3).
下面说一个O(n2)的:
代码如下:
// // main.cpp // SumSequencen2 // // Created by Alps on 14-7-23. // Copyright (c) 2014年 chen. All rights reserved. // #include <iostream> using namespace std; int MaxSubSequenceSum(const int A[], int N){ int MaxSum, ThisSum, i, j; MaxSum = 0; for (i = 0; i < N; i++) { ThisSum = 0; for (j = i; j < N; j++) { ThisSum += A[j]; MaxSum = MaxSum > ThisSum ? MaxSum : ThisSum; } } return MaxSum; } int main(int argc, const char * argv[]) { int A[] = {1, 2, -5, 2, 5, 1, 8, -4}; int N = sizeof(A)/sizeof(int); // printf("%d\n",N); int MaxSum = MaxSubSequenceSum(A, N); printf("%d\n",MaxSum); return 0; }这个也比较好理解,第一层循环就是i从头到尾遍历,第二层循环是j从i遍历到尾,在遍历过程中不断检测ThisSum的大小,取Max(ThisSum, MaxSum)的数,并赋值给MaxSum,这样就可以知道MaxSum是多少了~
还有一个方法复杂度是O(nlogn)但是这个算法比较麻烦,代码也比较麻烦,我这里没有写~想学的可以去《数据结构与算法分析》来学习。
这里有一个O(n)级别的算法来解决这个问题!!!:请看代码:
// // main.cpp // SumSequencen // // Created by Alps on 14-7-23. // Copyright (c) 2014年 chen. All rights reserved. // #include <iostream> using namespace std; int MaxSubSequenceSum(const int A[], int N){ int MaxSum, ThisSum, i; MaxSum = A[0]; ThisSum = 0; for (i = 0; i < N; i++) { ThisSum += A[i]; MaxSum = ThisSum > MaxSum ? ThisSum: MaxSum; if (ThisSum < 0) { ThisSum = 0; continue; } } return MaxSum; } int main(int argc, const char * argv[]) { int A[] = {1, 2, -5, 2, 5, 1, 8, -4}; int N = sizeof(A)/sizeof(int); // printf("%d\n",N); int MaxSum = MaxSubSequenceSum(A, N); printf("%d\n",MaxSum); return 0; }
O(n)级别的这类算法算是比较完美的算法了。我对这个算法的理解就是,在一个数组里,有很多很多段,这些段都有一个和,最小的段是一个元素,而最大的序列和肯定是一个段,或者是两个段的和,和就是加上一个正数就变大,所以当一个段是负数的时候,我就直接抛弃掉了~(除非所有都是负数,就找一个最大的。)
所以就有了上面的算法。。不懂的请留言~
算法-最长子序列和C/C++实现(三个复杂度)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。