Maximum Subarray (Kadane's Algorithm) at Amazon — Interview Guide

• Kadane: at each index, the best subarray ending here is either the element alone or the element plus the best ending at the previous index.
• Track the running sum, reset to 0 when it goes negative, and keep the global maximum.
• Divide-and-conquer gives O(n log n) and generalizes to 2D problems.

def max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

• Customer obsession — start from the customer and work backward.
• Ownership — think long-term and act on behalf of the whole company.
• Bias for action — make decisions with incomplete data and ship.
• Dive deep — understand the details behind any metric you cite.
• Deliver results — focus on the right inputs and hit commitments.