Leetcode——最长递增子序列(leetcode 300)

题目选择Leetcode 300 最长递增子序列

动态规划的典型例题，最长递增子序列

解题代码：C++

class Solution {public:int lengthOfLIS(vector<int>& nums) {int len = nums.size();int ans = -1;int dp[len];for(int i=0;i<len;i++){dp[i] = 1;for(int j=0;j<i;j++){if(nums[i] > nums[j] && (dp[i] < dp[j]+1))dp[i] = dp[j] + 1;}ans = max(ans,dp[i]);}return ans;}};

解题代码：C语言

int lengthOfLIS(int* nums, int numsSize){int dp[numsSize+1];int ans = 1;for(int i=0;i<numsSize;i++){dp[i] = 1;for(int j=0;j<i;j++){if(nums[i] > nums[j])dp[i] = dp[i] > (dp[j] + 1) ? dp[i] : (dp[j] + 1) ;}ans = dp[i]>ans? dp[i] : ans;}return ans;}