Skip to content

Laminal Arrays

01 · Question

An array's length is a positive power of two (including 1). Its laminal ranges are the whole array, the exact left/right halves of any laminal range, and the resulting singletons. Return the maximum sum among these nonempty ranges.

Examples: [3,-9,2,4,-1,5,5,-4] → 6 from [2,4]; [1] → 1; [-1,-2] → -1.

For four elements, the two-element ranges are indices [0,2) and [2,4); [1,3) is not allowed. This is not the usual maximum-subarray problem.

02 · Analysis

Helper contract: solve(left, right) returns (best sum among allowed ranges inside [left,right), sum of [left,right)). A singleton returns its value twice. For a larger range, the only candidates are a range in the left half, a range in the right half, or the whole current range.

Combine with total=leftTotal+rightTotal and best=max(leftBest,rightBest,total). Passing the total upward avoids a fresh range scan. Initializing best from real elements handles all-negative input; initializing it to zero would incorrectly allow an empty answer.

There are n leaves and n−1 internal nodes, each doing constant work: O(n) time and O(log n) stack space, with constant cost at n=1. A version that sums each current range separately costs O(n log n). Such a baseline must sum arr[left:right], not the entire original array at every call.

03 · Solution

Reference solution

1def max_laminal_sum(arr):
2    def solve(left, right):
3        if right - left == 1:
4            return arr[left], arr[left]
5        middle = (left + right) // 2
6        left_best, left_total = solve(left, middle)
7        right_best, right_total = solve(middle, right)
8        total = left_total + right_total
9        return max(left_best, right_best, total), total
10    best, _ = solve(0, len(arr))
11    return best
Previous
Lego Castle
Next
Fibonacci Number