本文主要是介绍LeetCode //C - 300. Longest Increasing Subsequence,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
300. Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Constraints:
- 1 <= nums.length <= 2500
- − 1 0 4 < = n u m s [ i ] < = 1 0 4 -10^4 <= nums[i] <= 10^4 −104<=nums[i]<=104
From: LeetCode
Link: 300. Longest Increasing Subsequence
Solution:
Ideas:
- We first handle the edge case where numsSize is 0.
- We allocate memory for the dp array and initialize each element to 1.
- We use a nested loop where the outer loop iterates through each element in nums, and the inner loop checks for all previous elements to find the length of the longest increasing subsequence that can end with nums[i].
- After finding the longest subsequence for each element, we update the maxLength accordingly.
- Finally, we free the allocated memory and return the maxLength.
Code:
int lengthOfLIS(int* nums, int numsSize) {if (numsSize == 0) return 0;// Allocate memory for the dp array and initialize all values to 1// since the minimum length of increasing subsequence can be 1.int *dp = (int *)malloc(numsSize * sizeof(int));for (int i = 0; i < numsSize; i++) {dp[i] = 1;}int maxLength = 1;for (int i = 1; i < numsSize; i++) {for (int j = 0; j < i; j++) {// If nums[i] is greater than nums[j], then it can form an increasing sequence// after the sequence ending with nums[j]. Update dp[i] if it forms a longer sequence.if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {dp[i] = dp[j] + 1;}}// Update the maximum length found so far.if (maxLength < dp[i]) {maxLength = dp[i];}}// Free the allocated memoryfree(dp);return maxLength;
}
这篇关于LeetCode //C - 300. Longest Increasing Subsequence的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!