Maximum Landing Sum
MediumDynamic Programming · Uber
Given an integer array values, you start at index 0 and must reach the last index. Each move goes forward by 1, or forward by a prime number whose last digit is 3 (3, 13, 23, 43, and so on). A move may not go past the last index.
Return the largest possible sum of values over every index you land on, including the start and the end.
Example 1
- Input:
- values = [5, -2, -4, 6, 1, -9]
- Output:
- 3
- Explanation
- Jump 3 from index 0 to index 3, then move 1 twice: 5 + 6 + 1 + (-9) = 3.
Example 2
- Input:
- values = [4, -8, -8, 10, -8, -8, 3]
- Output:
- 17
Example 3
- Input:
- values = [7]
- Output:
- 7
Constraints
- 1 ≤
values.length ≤ 3000 - -10000 ≤
values[i] ≤ 10000 - The answer fits in a 32-bit signed integer.