Leetcode 3165. Maximum Sum of Subsequence With Non-adjacent Elements
After each point update to an array, compute the maximum sum of a subsequence with no two adjacent elements (i.e., the maximum-weight independent set on a path) and return the sum of all query answers modulo 1e9+7. The challenge is to support up to 5·10^4 updates efficiently by maintaining range DP states (often with a segment tree / 2×2 max-plus matrices) to combine non-adjacent-selection choices in O(log n) per update.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
All Regions
Your account is free and you can post anonymously if you choose.