Difficulty with Dynamic Programming Approach for Longest Increasing Subsequence in C++ - Wrong Output for Edge Cases
I can't seem to get I'm trying to figure out After trying multiple solutions online, I still can't figure this out. I'm trying to implement the Longest Increasing Subsequence (LIS) algorithm using a dynamic programming approach in C++. My implementation seems correct at first glance, but I receive incorrect outputs for certain edge cases, particularly when the input array contains repeated elements. Here’s the code snippet I have: ```cpp #include <iostream> #include <vector> #include <algorithm> int lengthOfLIS(std::vector<int>& nums) { if (nums.empty()) return 0; std::vector<int> dp(nums.size(), 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); } } } return *std::max_element(dp.begin(), dp.end()); } int main() { std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18, 18}; std::cout << lengthOfLIS(nums) << std::endl; // Expected output is 5 return 0; } ``` The expected output for the input array `{10, 9, 2, 5, 3, 7, 101, 18, 18}` is `5` (for the subsequence `{2, 3, 7, 101, 18}`), but I get `4` instead. I suspect the scenario might be related to how I update the `dp` array, especially when dealing with repeated elements like the last two `18`s. I have verified that I am initializing `dp[i]` to `1` for all elements, and I'm also checking if the current number is greater than any previous one before updating. However, I wonder if I need to include additional conditions to handle the duplicates properly. I've tried adding a check to skip equal elements, but it didn't help. Can anyone provide insights into what I'm missing or how I can fix this scenario? I'm using g++ version 9.3.0 for compiling the code. My development environment is macOS. Am I missing something obvious? What are your experiences with this? Is there a simpler solution I'm overlooking? What would be the recommended way to handle this?