1.   给定一个数组，求最大的连续子序列和，O(n)时间与O(1)空间

2.   有一个坐标轴，上面有很多点，每个点有坐标，求长度为L的绳子最多能够覆盖几个点。

    两个指针,start，end。 

    如果points[front]-points[rear]<=L，头start向前移动一步。 

    如果points[front]-points[rear]>L，尾巴end向前移动一步。 

    每个数最多遍历2遍，因此时间复杂度为O(n)。 

int maxCover(int* a, int n, int l) 5 { 6     int maxCover = 1; 7     int begin = 0; 8     int end = 1; 9     while(end < n)10     {11         if(a[end] - a[begin] > l)12         {13             maxCover = (end - begin) > maxCover?(end - begin):maxCover;14             begin++;15         }16         else17             end++;18     }19     return maxCover;20 }

 

3.   求一个数组中第k 大的数

4.   最长公共序列

      

class LCS {public:    int findLCS(string A, int n, string B, int m) {        // write code here        int dp[n + 1][m + 1];        for(int i = 0; i <= n; i++){            dp[i][0] = 0;        }        for(int j = 0; j <= m; j++){            dp[0][j] = 0;        }                for (int i = 0; i < n; i++){            for (int j = 0; j < m; j++){                if (A[i] == B[j]){                    dp[i + 1][j + 1] = dp[i][j] + 1;                }                else{                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);                }            }        }        return dp[n][m];    }};

 

 

5.   最长递增子序列（Longest Increasing Subsequence）是指找到一个给定序列的最长子序列的长度，使得子序列中的所有元素单调递增。

      例如：{ 3，5，7，1，2，8 } 的 LIS 是 { 3，5，7，8 }，长度为 4。

 

思路：建立一个大小与 nums 长度相等的数组dp，用于记录每个 子序列的 最长长度，即 dp[i] 表示nums 第 0 个到第 i 个元素中以 nums[i]为最大值的最长子序列长度（注意序列的最后一个值为 nums[i]）：

感觉底下的这个图不对。。

      

 

//  状态转移方程    dp[i] = max{dp[j]+1，dp[i]}, j

dp(n, 1); // 初始化为1 for(int i = 1; i < n; i++){ //dp[i]表示LIS的长度。nums[i]作为LIS的最后一个元素。 for(int j = 0;j < i; j++) { if(nums[i] > nums[j]) { //满足递增 dp[i]=max(dp[i], dp[j] + 1); //利用状态转移方程 } } } int res=0; for(int i = 0;i < n; i++) {

//求得最大的dp[i] res = max(res, dp[i]); } return res; }};