输入一个数组,输出最长升序子序列的长度。
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; } }
#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; }