Implement Prefix Sums and KadaneStep 4 of 5

Kadane's Maximum Subarray

12345

Step 4: Kadane's Maximum Subarray

Find the largest sum of any contiguous subarray with Kadane's algorithm in O(n).

Write max_subarray(nums):

  • Track the best subarray sum ending at the current index: current = max(x, current + x).
  • Track the overall best: best = max(best, current).
  • Initialize both to nums[0] and scan the rest.

This handles the all-negative case correctly: it returns the largest single element rather than 0.

Hints
Starter code
class RangeSum:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

    def query(self, i, j):
        return self.prefix[j + 1] - self.prefix[i]


def subarray_sum_equals_k(nums, k):
    counts = {0: 1}
    running = 0
    total = 0
    for x in nums:
        running += x
        total += counts.get(running - k, 0)
        counts[running] = counts.get(running, 0) + 1
    return total


class DiffArray:
    def __init__(self, n):
        self.n = n
        self.diff = [0] * (n + 1)

    def add(self, i, j, delta):
        self.diff[i] += delta
        self.diff[j + 1] -= delta

    def result(self):
        out = []
        running = 0
        for k in range(self.n):
            running += self.diff[k]
            out.append(running)
        return out


def max_subarray(nums):
    """Return the maximum sum of any contiguous subarray."""
    # TODO: Kadane's algorithm, initializing best and current to nums[0]
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step