Max Subarray Sum

Python data engineering interview problem. Difficulty: beginner. Pattern: Dynamic Programming. About 10 minutes. Free to practice.

Maximum sum of any contiguous subarray (Kadane). Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

You have a list of numbers that can be positive or negative, for example the daily profit or loss of a shop. You want to find the best stretch of days in a row: the group of neighbouring numbers with the largest total. Write a function max_subarray(nums) that returns the largest sum you can get from a continuous part of the list (a subarray). The part must contain at least one number. For [-2, 1, -3, 4, -1, 2, 1, -5, 4] the best part is [4, -1, 2, 1], with a sum of 6. Keep the print lines in the editor.

Requirements

• Return the largest sum of numbers that sit next to each other in the list.
• The part must have at least one number.
• Return the sum itself, not the numbers that make it up.

Constraints

• The list has at least one element.
• Negative numbers are allowed.
• The subarray has to be continuous. You cannot skip numbers in the middle.

Examples

Input: max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) Output: 6 Best window is 4,-1,2,1.

Topics: lakebench, python, kadane, subarray.

More Python interview questions · All interview problems · Learn data engineering