Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

ReturnlongestIncreasingSubsequence fromdpLongestIncreasingSubsequence#1164

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Open
shola wants to merge3 commits intotrekhleb:master
base:master
Choose a base branch
Loading
fromshola:refactor/dpLongestIncreasingSubsequence

Conversation

shola
Copy link

@sholashola commentedAug 22, 2024
edited
Loading

The Longest Increasing SubsequenceREADME.md anddpLongestIncreasingSubsequence.test.js give examples of the longest increasing subsequence that will be generated from various sequences:

In the first 16 terms of the binary Van der Corput sequence

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

a longest increasing subsequence is

0, 2, 6, 9, 11, 15.

However, the implemented algorithm only returns the length of the longest increasing subsequence, not the subsequence itself. This change will create thelongestIncreasingSubsequence from thelengthsArray and return that instead oflongestIncreasingLength.

The tests have been updated to expect a subsequence instead of length.

Copy link

@jessbennettjessbennett left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

❇️

shola reacted with heart emoji
@shola
Copy link
Author

@trekhleb what do you think of this change?

Copy link

@dcq01dcq01 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Hi! I'm a grad student working on a research project about using large language models to automate code review. Based on your commit476a47e and the changes in src/algorithms/sets/longest-increasing-subsequence/test/dpLongestIncreasingSubsequence.test.js, my tool generated this comment:

  1. Input Validation: Ensure that thedpLongestIncreasingSubsequence function properly validates its input, handling unexpected types (e.g., non-numeric values) to prevent potential type coercion issues or runtime errors.
  2. Error Handling: The implementation ofdpLongestIncreasingSubsequence should include error handling to manage edge cases, such as an empty array or an array with non-integer values.
  3. Expected Output Correction: The expected output for a strictly decreasing array should be an empty array[] or the longest increasing subsequence found, which is not applicable here. Review the expected output to ensure it aligns with the function's intended behavior.
  4. Test Description Update: Update the test description to "should return the longest increasing subsequence" to accurately describe the expected behavior of the function.
  5. Additional Test Cases: Consider adding more test cases to cover various scenarios, including strictly increasing, strictly decreasing, and mixed sequences, as well as edge cases like empty arrays or arrays with all identical elements.
  6. Expect Statement Clarity: Ensure that the expected output matches the function's intended return value. If the function returns the subsequence, the expected output should be the subsequence itself, and if it returns the length, the expected output should be the length.
  7. Algorithm Complexity: If thedpLongestIncreasingSubsequence function is currently implemented with a time complexity of O(n^2), consider refactoring it to use a more efficient O(n log n) approach.
  8. Performance Considerations: Ensure that the function has appropriate limits on input size and handles large datasets efficiently to prevent denial-of-service vulnerabilities.
  9. Memory Optimization: Ensure that the function only maintains the necessary elements in memory, avoiding unnecessary storage of all subsequences.
  10. Modular Test Structure: Consider organizing tests into separate describe blocks or files if there are multiple functionalities related to the longest increasing subsequence.

As part of my research, I'm trying to understand how useful these comments are in real-world development. If you have a moment, I'd be super grateful if you could quickly reply to these two yes/no questions:

  1. Does this comment provide suggestions from a dimension you hadn’t considered?
    1. Do you find this comment helpful?

Thanks a lot for your time and feedback! And sorry again if this message is a bother.

Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment
Reviewers

@dcq01dcq01dcq01 left review comments

@andrzejsydorandrzejsydorandrzejsydor approved these changes

@jessbennettjessbennettjessbennett approved these changes

@anandfreshanandfreshanandfresh approved these changes

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

5 participants
@shola@andrzejsydor@jessbennett@anandfresh@dcq01

[8]ページ先頭

©2009-2025 Movatter.jp