DSA Factory
Free Recursion lessonsRecursion · Stage 2 · Divide and conquer · Step 1

The best stretch, half by half

Find the stretch of neighbouring values with the biggest total by solving each half and then the stretches that cross the middle. About 16 minutes.

Three places the best can hide

Given a list of numbers, some negative, which run of neighbouring values has the biggest total? Split the list in the middle. The best run is in one of three places: completely inside the left half, completely inside the right half, or crossing the split.

The first two are the same question on a shorter list, so recurse. The third needs a small extra calculation.

Left half: recurse.
Right half: recurse.
Crossing: a short loop out from the middle.
In code
def biggest(lo, hi):
    if lo == hi:
        return nums[lo]
    mid = (lo + hi) // 2
    left = biggest(lo, mid)
    right = biggest(mid + 1, hi)
    return max(left, right)
Best stretch of 3, -4, 2, 5, -1, -2, 4, -3.
3
0
-4
1
2
2
5
3
-1
4
-2
5
4
6
-3
7
leftright

Split into 3, -4, 2, 5 and -1, -2, 4, -3. The best stretch is in the left, in the right, or across the split.

Move 1 of 5

The crossing stretch

A crossing stretch must include the last value of the left half and the first value of the right half. So it is the best stretch ending at the middle on the left plus the best stretch starting just after the middle on the right.

Find each by walking outwards from the middle, adding values and remembering the biggest total seen. Add the two bests together.

Left part: walk left from the middle, keep the best total.
Right part: walk right from just after the middle, keep the best total.
In code
total, best = 0, nums[mid]
for i in range(mid, lo - 1, -1):
    total += nums[i]
    best = max(best, total)
Quick check

A stretch crosses the middle of a split. Which two positions must it include?

  1. AThe last position of the left half and the first of the right
  2. BThe first position of the whole list
  3. CAny two positions
Show the answer

The last position of the left half and the first of the right. To cross the split, a stretch must reach from one side to the other without gaps.

Your problem

Best stretch

nums is a list of whole numbers with at least one value, some of them possibly negative. A stretch is one or more neighbouring values. Return the biggest total of any stretch, using a recursive function that splits the list in half.

Example
nums = [-2, 1, -3, 4, -1, 2, 1, -5] → 6

1 ≤ length ≤ 100,000 · −1,000 ≤ value ≤ 1,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve