Maximum Sum of Two Non-Overlapping Subarrays

Establish the variant first

The title alone does not say whether the two subarrays have fixed lengths, whether their lengths differ, or whether they may be empty. Ask that before committing. For the common fixed-length variant, use prefix sums to get every window sum in O(1). Build leftBest[i], the best eligible first window ending at or before i, and rightBest[i], the best eligible second window starting at or after i. Then evaluate each valid split and combine a left value with a right value.

Preserve non-overlap

The index offsets must ensure the two windows do not share an element; write those boundaries explicitly rather than relying on intuition. For variable-length maximum-sum subarrays, compute Kadane-style best prefixes and suffixes instead. State which version you are solving after clarification. Prefix construction and the split scan are O(n) time and O(n) space; with careful rolling state, some fixed-length forms reduce the extra space. Test adjacent windows, negative values, and the smallest array that can contain both choices.