Lintcode 1850 Pick Apples
https://www.lintcode.com/problem/1850
Alice and Bob work in a beautiful orchard. There are N apple trees in the orchard. The apple trees are arranged in a row and they are numbered from 1 to N.
Alice is planning to collect all the apples from K consecutive trees and Bob is planning to collect all the apples from L consecutive trees.
They want to choose to disjoint segements (one consisting of K trees of Alice and the other consisting of L trees for Bob) so as not to disturb each other. you should return the maximum number of apples that they can collect.- N is an integer within the range: [2, 600]
- K and L are integers within the range: [1, N - 1]
- each element of array A is an integer within the range: [1, 500]Since Alice and Bob are working on separate consecutive apple trees without overlap, I thought of using sliding window to solve this problem. We can iterate all the possible dividers in the array, and each iteration, we find the max value from left subarray and right subarray given the length of the sliding window.
The time complexity is O(n^2) since we kind of have a nested for loop. But the it should be OK judging from the size of the array which is [2, 600]. Even for O(n^2) the overall time complexity is 600 * 600 which is around 10^5 level. This should be fine, in fact the solution actually works and was accepted.
One thing to note is when we have a divider, we should consider Alice on left and Bob on right AND Alice on right and Bob on left.
Let’s take a look at the solution:
from typing import (
List,
)
class Solution:
"""
@param a: a list of integer
@param k: a integer
@param l: a integer
@return: return the maximum number of apples that they can collect.
"""
def pick_apples(self, a: List[int], k: int, l: int) -> int:
if l + k > len(a):
return -1
def max_apples(left: int, right: int, n: int):
sum = 0
result = 0
for i in range(left, right):
if i - left <= n - 1:
sum += a[i]
else:
result = max(result, sum);
sum = sum + a[i] - a[i - n]
return max(result, sum);
result = 0
for divide in range(0, len(a)):
left_apples_l = max_apples(0, divide, l)
left_apples_k = max_apples(0, divide, k)
right_apples_l = max_apples(divide, len(a), l)
right_apples_k = max_apples(divide, len(a), k)
result = max(result, left_apples_l + right_apples_k, left_apples_k + right_apples_l)
return result