implementing Finding Longest Increasing Subsequence in C++ - Incorrect Output for Edge Cases
I've been struggling with this for a few days now and could really use some help. I'm trying to implement an algorithm to find the longest increasing subsequence (LIS) in a given array of integers using dynamic programming in C++. My current implementation seems to yield incorrect results for certain edge cases, particularly when the input array contains duplicates or is strictly decreasing. For instance, for the input `[3, 3, 2, 1, 0]`, I expect the LIS to be `[3]`, but my code returns `1`. Here's the code I have so far: ```cpp #include <vector> #include <iostream> #include <algorithm> int lengthOfLIS(std::vector<int>& nums) { if (nums.empty()) return 0; std::vector<int> dp(nums.size(), 1); int maxLength = 1; for (int i = 1; i < nums.size(); ++i) { for (int j = 0; j < i; ++j) { if (nums[i] > nums[j]) { dp[i] = std::max(dp[i], dp[j] + 1); } } maxLength = std::max(maxLength, dp[i]); } return maxLength; } int main() { std::vector<int> nums = {3, 3, 2, 1, 0}; std::cout << "Length of LIS: " << lengthOfLIS(nums) << std::endl; return 0; } ``` I've tried different approaches, including using binary search for optimization, but I keep running into similar issues. I suspect the question may lie in how I'm handling the updates of the `dp` array, especially since duplicates can cause my logic to break. Can anyone guide to identify where the scenario is in this implementation? Additionally, are there any best practices for handling edge cases when implementing LIS? Thanks in advance! Is there a better approach?