题解 | #最长上升子序列(一)#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 给定数组的最长严格上升子序列的长度。
 * @param arr int整型一维数组 给定的数组
 * @param arrLen int arr数组长度
 * @return int整型
 */
int LIS(int* arr, int arrLen ) {
    // write code here
    if(arrLen == 0) return 0;
    int* dp = (int*)malloc(sizeof(int) * arrLen);
    for(int i = 0; i < arrLen; i++) {
        dp[i] = 1;
    }
    int max = 1;
    for(int i = 1; i < arrLen; i++) {
        for(int j = 0; j < i; j++) {
            if(arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
        if(dp[i] > max) {
            max = dp[i];
        }
    }
    return max;
}