Maximum Apples from Two Disjoint Fixed-Length Segments
Updated
Problem statement
There are N apple trees in a row. Tree i has A[i] apples. Alice collects all apples from exactly K consecutive trees, and Bob collects all apples from exactly L consecutive trees.
Choose the two groups of trees so they do not overlap and their total number of apples is as large as possible. The groups may be next to each other, and either group may come first.
For this exercise, assume the result is -1 if the two non-overlapping groups do not fit. Otherwise, first maximize the actual apple total, then return that maximum modulo 10^9 + 7.
Function
solution(A: int[], K: int, L: int) → intExamples
Example 1
A = [6,1,4,6,3,2,7,4]K = 3L = 2return = 24Using one-based tree numbers, Alice takes trees 3 through 5 for 4 + 6 + 3 = 13 apples, and Bob takes trees 7 through 8 for 7 + 4 = 11. The total 24 is optimal.
Example 2
A = [10,19,15]K = 2L = 2return = -1The two required segments contain four trees, but only three trees exist.
Example 3
A = [1000000000,8,7]K = 1L = 1return = 1This example chooses the actual maximum 1000000008, whose remainder is 1. Choosing the largest remainder first would incorrectly prefer 8 + 7 = 15.
Constraints
2 <= A.length <= 100000.1 <= K, L <= A.length - 1.1 <= A[i] <= 10^9.
More Marshall Wace Online Assessment questions
- Count Letters with Ordered Lowercase and Uppercase OccurrencesOA · Seen Oct 2025
- Maximum Trailing Zeros on a Path with at Most One TurnOA · Seen Oct 2025
- Shortest Subarray Covering an Integer RangeOA · Seen Oct 2025
- Maximum Events in a 60-Second WindowOA · Seen Aug 2025
- Successful Logins from Multiple CountriesOA · Seen Aug 2025
- Maximize Remaining Item Types After Clearing Consecutive ShelvesOA · Seen Nov 2024
- Shortest String After Erasing Equal PairsOA · Seen Nov 2024
- Count Distinct Tags in a Fixed-Radius Circle (Practice Reconstruction)OA · Seen Apr 2024
- Generate Unique Company Email AddressesOA · Seen Apr 2024
- Reconstruct a Two-Row Binary MatrixOA · Seen Apr 2024
Similar questions at other companies
- Minimize Sum of Distances to WarehousesAmazon · OA
- Maximum Non-Decreasing Array LengthVisa · OAVisa interview questions
- Maximize CollaborationTikTok · OATikTok interview questions
- Maximum Sum RectangleDeloitte · OADeloitte interview questions
- Maximum Subarray Sum with Equal EndpointsGoogle · ONSITE INTERVIEWGoogle interview questions
- Maximum Subarray SumCapital One · PHONE SCREEN · ONSITE INTERVIEWCapital One interview questions
- Largest All-One Square Area and CountNVIDIA · PHONE SCREENNVIDIA interview questions
- Most Visited Sprint MarkerMicrosoft · OAMicrosoft interview questions
- 0/1 KnapsackConfluent · OAConfluent interview questions
- Minimum Cost to Tile a Strip with Widths 1, 2, and 3Infosys · OAInfosys interview questions