1子序列的最大和

給定一個整數(shù)數(shù)組 nums 岸霹，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和将饺。

示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大贡避，為 6。

int maxSubArray(int* nums, int numsSize){
    int max = nums[0];
    int sum = nums[0];
    int tmp;
    for(int i=1; i< numsSize; i++){
        sum = nums[i] + (sum > 0 ? sum : 0);
        max = sum > max ? sum : max;
    }
    return max;
}

2俯逾、最長遞增子序列

給定一個無序的整數(shù)數(shù)組贸桶，找到其中最長上升子序列的長度舅逸。
示例:

輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]桌肴，它的長度是 4。
說明:

可能會有多種最長上升子序列的組合琉历，你只需要輸出對應(yīng)的長度即可坠七。
你算法的時間復(fù)雜度應(yīng)該為 O(n2) 水醋。

int lengthOfLIS_01(int* nums, int numsSize) {
    if (numsSize < 2) {
        return numsSize;
    }
    int lis[numsSize];

    int i, j, result = 0;
    for (i = 0; i < numsSize; i++) {
        lis[i] = 1;
        for (j = 0; j < i; j++) {
            if (nums[i] > nums[j] && lis[j] + 1 > lis[i]) {
                lis[i] = lis[j] + 1;
            }
        }
        result = result > lis[i] ? result : lis[i];
    }
    return result;
}

3、最長公共子序列

int LCS(char x[],char y[])
{
    int i,j;
    int x_len,y_len;
    x_len = strlen(x);
    y_len = strlen(y);

    for(i = 1;i <= x_len;i++)
    {
        for(j = 1;j <= y_len;j++)
        {
            if(x[i-1] == y[j-1])
            {
                c[i][j] = c[i-1][j-1] +1;
                b[i][j] = 0;
            }
            else
            {
                c[i][j] = Max(c[i-1][j],c[i][j-1],i,j);
            }
        }
    }
        return c[x_len][y_len];
}

4彪置、最小編輯距離

int cmp_levenshtein( const char *s1, const char *s2 )
{
    int row = strlen(s1);               /* s1 的長度 */
    int col = strlen(s2);               /* s2 的長度 */

    int mat[row][col];                  /* C99 - variable-length array */

    for( int i=0; i<row; ++i ) {        /* 數(shù)組的行 */
        for( int j=0; j<col; ++j ) {    /* 數(shù)組的列 */
            if( i == 0 ) {
                mat[i][j] = j;          /* 初始化第1行為 [ 0 1 2 ... ] */
            }
            else if( j == 0 ) {
                mat[i][j] = i;          /* 初始化第1列為 [ 0 1 2 ... ] */
            }
            else {
                int cost = ( s1[i-1] == s2[j-1] ) ? 0 : 1;     /* 記錄s1[i-1]與s2[j-1]是否相等 */
                mat[i][j] = MIN3( mat[i-1][j  ] + 1,           /* 取三者的最小值 */
                                  mat[i  ][j-1] + 1,
                                  mat[i-1][j-1] + cost);
            }
        }
    }

    return mat[row-1][col-1];
}