Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Dynamic programming

The best segment ending here

Lesson · 9 min read · Dynamic programming · Pattern: the best segment ending here

For the best contiguous stretch, compute the best stretch ending at each position: extend the previous one or start again.

The pattern

"The best contiguous stretch" (the largest-sum subarray, the best single trade, the longest valid run) can end anywhere. Fix the end: let end(i) be the best stretch ending exactly at i. There are only two ways to have one: extend the best stretch ending at i − 1, or start a new one at i.

Best ending here

end(i)

  1. = opt( extend: end(i − 1) ⊕ x[i], restart: x[i] ).

answer

  1. the best end(i) over all i: no single entry holds it.

For the maximum sum this is Kadane's algorithm: end(i) = max(end(i − 1) + x[i], x[i]).

Worked example: the largest-sum subarray

Kadane on [−2, 1, −3, 4, −1, 2, 1, −5, 4].

  1. Step 1 / 9
    nums
    -2011-3243-142516-5748
    end
    -20·1·2·3·4·5·6·7·8

    Base case: end[0] = -2.

  2. Step 2 / 9
    nums
    -2011-3243-142516-5748
    end
    -2011·2·3·4·5·6·7·8

    Restart at 1 (extending would give -1).

  3. Step 3 / 9
    nums
    -2011-3243-142516-5748
    end
    -2011-22·3·4·5·6·7·8

    Extend: 1 + -3 = -2.

  4. Step 4 / 9
    nums
    -2011-3243-142516-5748
    end
    -2011-2243·4·5·6·7·8

    Restart at 4 (extending would give 2).

  5. Step 5 / 9
    nums
    -2011-3243-142516-5748
    end
    -2011-224334·5·6·7·8

    Extend: 4 + -1 = 3.

  6. Step 6 / 9
    nums
    -2011-3243-142516-5748
    end
    -2011-22433455·6·7·8

    Extend: 3 + 2 = 5.

  7. Step 7 / 9
    nums
    -2011-3243-142516-5748
    end
    -2011-2243345566·7·8

    Extend: 5 + 1 = 6.

  8. Step 8 / 9
    nums
    -2011-3243-142516-5748
    end
    -2011-224334556617·8

    Extend: 6 + -5 = 1.

  9. Step 9 / 9
    nums
    -2011-3243-142516-5748
    end
    -2011-22433455661758

    Extend: 1 + 4 = 5. The best entry is 6: the stretch 4, −1, 2, 1.

Variations

  • Products: a negative number turns the smallest product into the largest, so keep both the best and the worst ending here.
  • Circular arrays: the best wrap-around stretch is the total minus the worst ordinary stretch.
  • One buy, one sell: the best profit ending at day i is price[i] minus the lowest price so far.
TimeO(n)
SpaceO(1)

The problems in this module: