Crash Code Part-9 (Maximum Apples, Disjoint Segments)

Problem Description

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 two disjoint segments (one consisting of K trees for Alice and the other consisting of L trees for Bob) so as not to disturb each other. What is the maximum number of apples that they can collect?

Write a function:def solution(A, K, L) that, given an array A consisting of N integers denoting the number of apples on each apple tree in the row, and integers K and L denoting, respectively, the number of trees that Alice and Bob can choose when collecting, returns the maximum number of apples that can be collected by them, or −1 if there are no such intervals.

Examples

Sample Case 0

A = [6, 1, 4, 6, 3, 2, 7, 4]
K = 3
L = 2

Your function should return: 24

One optimal choice is:

• Alice chooses trees 3 to 5: 4 + 6 + 3 = 13
• Bob chooses trees 7 to 8: 7 + 4 = 11

The total is: 13 + 11 = 24

Sample Case 1

A = [10, 19, 15]
K = 2
L = 2

Your function should return:-1, because it is not possible for Alice and Bob to choose two disjoint intervals.

Constraints

• N is an integer within the range [2..100]
• K and L are integers within the range [1..N - 1]
• Each element of A is an integer within the range [1..500]

The objective is correctness, but the solution below is also efficient and runs in linear time.

Approach

The key observation is that the two segments can only appear in one of two orders:

• Alice’s K-tree segment comes before Bob’s L-tree segment.
• Bob’s L-tree segment comes before Alice’s K-tree segment.

We can solve both cases in O(N) time.

Step 1: Build prefix sums

Define:prefix[i] = sum of A[0:i]

Then the sum of any half-open range [left:right] is:prefix[right] - prefix[left]

So the sum of a segment of length size starting at i is:prefix[i + size] - prefix[i]

Step 2: Maximize the left segment

Suppose a segment of length left_size must be completely before a segment of length right_size.

For every possible position of the right segment, keep track of the maximum sum of any valid left segment that ends before it.

For example, while scanning the possible right segment starts, maintain:best_left as the largest sum of a left_size segment seen so far.

Then the best total for that right segment is:best_left + current_right_sum

Step 3: Check both orders

We run the same scan twice:

(K before L)
(L before K)

The larger result is the answer.

If K + L > N, the two required segments cannot both fit, so we immediately return -1.

Solve

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

def solution(A, K, L):
    n = len(A)

    # Two disjoint segments cannot fit in the array.
    if K + L > n:
        return -1

    # Prefix sums: prefix[i] is the sum of A[0:i].
    prefix = [0] * (n + 1)

    for i, value in enumerate(A):
        prefix[i + 1] = prefix[i] + value

    def segment_sum(start, length):
        return prefix[start + length] - prefix[start]

    def max_in_order(left_size, right_size):
        # Find the best total when the left_size segment
        # is completely before the right_size segment.

        best_left = segment_sum(0, left_size)
        best_total = -1

        for right_start in range(
            left_size,
            n - right_size + 1
        ):
            left_start = right_start - left_size

            best_left = max(
                best_left,
                segment_sum(left_start, left_size)
            )

            right_sum = segment_sum(right_start, right_size)

            best_total = max(
                best_total,
                best_left + right_sum
            )

        return best_total

    # Try both possible orders.
    return max(
        max_in_order(K, L),
        max_in_order(L, K)
    )


if __name__ == '__main__':
    import sys

    data = sys.stdin.read().strip().split()

    if data:
        n = int(data[0])
        A = list(map(int, data[1:n + 1]))
        K = int(data[n + 1])
        L = int(data[n + 2])

        print(solution(A, K, L))

Why This Solution Is Correct

Consider the optimal pair of disjoint segments.

Because the trees are arranged in a line, exactly one of these statements must be true:

• the K-length segment is entirely to the left of the L-length segment, or
• the L-length segment is entirely to the left of the K-length segment.

The helper max_in_order(left_size, right_size) examines one of these orders.

For every possible starting position of the right segment:

1. best_left contains the maximum sum of any valid left segment ending before that right segment.
2. right_sum is the sum of the current right segment.
3. Therefore, best_left + right_sum is the best total for that right-segment position.

Taking the maximum over every position gives the optimal arrangement for that order.

Finally, evaluating both possible orders guarantees that the globally optimal pair is considered.

If K + L > N, two disjoint segments cannot fit, so returning -1 is necessary and correct.

Complexity Analysis

Let N = len(A).

Time Complexity

Building the prefix-sum array takes:O(N)

Each call to max_in_order scans the array once:O(N)

We call it twice, once for each segment order, so the total remains:O(N)

Space Complexity

The prefix-sum array contains N + 1 values:O(N)

No additional data structure proportional to the number of segment pairs is required.

Why Prefix Sums Help

A naive implementation might repeatedly calculate the sum of every K- or L-tree segment.

For a segment:A[start:start + length]

summing all values directly costs O(length).

Using prefix sums reduces every segment-sum query to constant time:prefix[start + length] - prefix[start]

That lets the algorithm scan all candidate positions in linear time.