Hackbright Code Challenges

Largest Subsequence Sum: Solution

Largest Subsequence Sum: Solution

Problem

Largest Subsequence Sum

Whiteboard

Harder

Challenge

Medium

Concepts

General

Download

largest-sum-solution.zip


def largest_sum(nums):
    """Find subsequence with largest sum."""

    # START SOLUTION

    # Our best (update as we find new bests)
    best_sum = 0
    start_of_best = 0
    end_of_best = -1  # (nothing)

    # Current sum and start
    current_sum = 0
    start_of_curr = 0

    for i, n in enumerate(nums):
        current_sum += n

        if current_sum > best_sum:
            # Best so far -- record this sum & its start and end
            best_sum = current_sum
            start_of_best = start_of_curr
            end_of_best = i

        if current_sum <= 0:
            # Dropped belonw 1, so we can't improve -- reset
            # start_of_best, to begin with next number
            start_of_curr = i + 1
            current_sum = 0

    return nums[start_of_best:end_of_best + 1]