Partition Array for Maximum Sum
Medium · Dynamic Programming · about 20 minutes
Asked at ByteDance, Google, Meta, Bloomberg, Amazon.
Cut arr into consecutive pieces, none longer than k. Then overwrite every element of each piece with that piece's largest value. Choose the cuts so the array's new total is as big as possible, and return that total (it fits in a signed 32-bit integer).