最长升序子序列

[编程题]最长升序子序列

热度指数：384 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

输入一个数组，输出最长升序子序列的长度。

输入描述:

一组数组，长度不大于

输出描述:

一个整数，最长升序子序列的长度

示例1

输入

5,1,4,2,3

输出

说明

最长升序子序列为1,2,3，长度为3

算法知识视频讲解

pein531

采用动态规划

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null){
            String[] strArr = line.split(",");
            int[] arr = new int[strArr.length];
            for(int i = 0; i < strArr.length; i++) arr[i] = Integer.parseInt(strArr[i].trim());
            System.out.println(solve(arr));
        }
    }
    
    private static int solve(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];   // dp[i]用于存储以nums[i]结尾的最长上升子序列的最大长度
        dp[0] = 1;
        int maxLen = 1;
        for(int i = 0; i < nums.length; i ++){
            int maxSubLen = 0;
            for(int j = 0; j < i; j ++){
                if(nums[j] < nums[i])
                    maxSubLen = Math.max(maxSubLen, dp[j]);
            }
            dp[i] = maxSubLen + 1;
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}

发表于 2020-10-19 13:25:55 回复(0)

Python

查家大少爷

s=list(map(int, input().split(",")))
n=len(s)
dp=[1]#当前数字存在于序列中的最长递增子序列
dp1=[1]#
dp2=[s[0]]#从大到小排序的元素

for i in range(1,n):

#二分法

x=s[i]
low=0
high=len(dp1)-1
while low<=high:
mid=int((low+high)/2)
if x==dp2[mid]:
dp.append(dp2[mid])
break
elif x<dp2[mid]:
high=mid-1
elif x>dp2[mid]:

low=mid+1

#插入新元素

if low>high:
dp1.append(0)
dp2.append(0)
for k in range(len(dp1)-1,low,-1):
dp1[k]=dp1[k-1]
dp2[k]=dp2[k-1]
acc=1
if low!=0:
acc=max(dp1[:low]) + 1
dp.append(acc)
dp1[low]=acc
dp2[low]=x
print(max(dp))

编辑于 2020-09-01 22:06:31 回复(0)

C/C++

天命剑主

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

#define INF_INT 0x7fffffff
/**
 * 最长递增子序列(复杂度nlog(n))
 * @param a 序列
 * @param n 序列长度
 * @return 最长递增子序列长度
 */
int longest_increasing_subsequence_efficient(const int *a, int n) {
    auto *dp = new int[n];
    fill(dp, dp + n, INF_INT);
    for (int i = 0; i < n; i++) {
        *lower_bound(dp, dp + n, a[i]) = a[i];
    }
    int result = static_cast<int>(lower_bound(dp, dp + n, INF_INT) - dp);
    delete[] dp;
    return result;
}

int main() {
    int sequence[100000];
    int len = 0;
    string s;
    getline(cin, s);// 此题输入不规范，有些用例有空格，有些输入没有空格
    size_t pos = -1;//size_t是非负类型，这里的-1并不是-1，但是pos+1之后溢出，仍然是0
    do {
        sequence[len++] = (int) strtol(s.c_str() + pos + 1, nullptr, 10);
    } while ((pos = s.find(',', pos + 1)) != string::npos);
    int ans = longest_increasing_subsequence_efficient(sequence, len);
    cout << ans << endl;
}

编辑于 2020-01-08 10:45:55 回复(0)