The Best Run Before and After in Python, Java and TypeScript

The same question answered twice in each language: every range added up, then one pass, each printing its answer and how many additions it made.

Each listing answers the best run of consecutive days twice, once by adding up every range and once in a single pass with the lowest total so far, and counts the additions each makes, because a count of the dominant operation repeats from run to run where a time would not. The highlighted line in each version is the one that dominates: the innermost addition in the range version, and the single update per day in the one pass. Each runs on the profits 5, −7, 4, 2, −3, 6, −8, 3.

The best run before and after in three languages

best_run_before_after.pypy

def best_run_every_range(profits: list[int]) -> tuple[int, int]:
    additions = 0
    best = profits[0]
    for start in range(len(profits)):
        for end in range(start, len(profits)):
            total = 0
            for day in range(start, end + 1):
                total += profits[day]
                additions += 1
            best = max(best, total)
    return best, additions


def best_run_one_pass(profits: list[int]) -> tuple[int, int]:
    additions = 0
    total, lowest, best = 0, 0, profits[0]
    for profit in profits:
        total += profit
        additions += 1
        best = max(best, total - lowest)
        lowest = min(lowest, total)
    return best, additions


profits = [5, -7, 4, 2, -3, 6, -8, 3]
print("every range: best %d, additions %d" % best_run_every_range(profits))
print("one pass:    best %d, additions %d" % best_run_one_pass(profits))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

every range: best 9, additions 120
one pass:    best 9, additions 8

BestRunBeforeAfter.javajava

public class BestRunBeforeAfter {
    record Result(int best, int additions) {}

    static Result everyRange(int[] profits) {
        int additions = 0;
        int best = profits[0];
        for (int start = 0; start < profits.length; start++) {
            for (int end = start; end < profits.length; end++) {
                int total = 0;
                for (int day = start; day <= end; day++) {
                    total += profits[day];
                    additions++;
                }
                best = Math.max(best, total);
            }
        }
        return new Result(best, additions);
    }

    static Result onePass(int[] profits) {
        int additions = 0;
        int total = 0, lowest = 0, best = profits[0];
        for (int profit : profits) {
            total += profit;
            additions++;
            best = Math.max(best, total - lowest);
            lowest = Math.min(lowest, total);
        }
        return new Result(best, additions);
    }

    public static void main(String[] args) {
        int[] profits = {5, -7, 4, 2, -3, 6, -8, 3};
        Result slow = everyRange(profits);
        Result fast = onePass(profits);
        System.out.printf("every range: best %d, additions %d%n", slow.best(), slow.additions());
        System.out.printf("one pass:    best %d, additions %d%n", fast.best(), fast.additions());
    }
}

OutputRan with eclipse-temurin:25.0.4.1_1-jdk-noble (Java 25.0.4.1)

every range: best 9, additions 120
one pass:    best 9, additions 8

best_run_before_after.tsts

type Result = { best: number; additions: number };

function everyRange(profits: number[]): Result {
  let additions = 0;
  let best = profits[0];
  for (let start = 0; start < profits.length; start++) {
    for (let end = start; end < profits.length; end++) {
      let total = 0;
      for (let day = start; day <= end; day++) {
        total += profits[day];
        additions++;
      }
      best = Math.max(best, total);
    }
  }
  return { best, additions };
}

function onePass(profits: number[]): Result {
  let additions = 0;
  let total = 0, lowest = 0, best = profits[0];
  for (const profit of profits) {
    total += profit;
    additions++;
    best = Math.max(best, total - lowest);
    lowest = Math.min(lowest, total);
  }
  return { best, additions };
}

const profits = [5, -7, 4, 2, -3, 6, -8, 3];
const slow = everyRange(profits);
const fast = onePass(profits);
console.log(`every range: best ${slow.best}, additions ${slow.additions}`);
console.log(`one pass:    best ${fast.best}, additions ${fast.additions}`);

OutputRan with node:24.22.0-trixie-slim (Node 24.22.0), TypeScript 5.9.3

every range: best 9, additions 120
one pass:    best 9, additions 8

Both versions agree on 9, and the counts are 120 and 8. The one pass needs no more memory than the range version: three numbers, O(1) extra, the case where speed costs nothing. Both start best at the first day's figure rather than at 0, so a stall that only loses money reports its smallest loss rather than an empty run. Java's int and TypeScript's number hold these totals exactly; for totals past about 2.1 × 10⁹, Java would need long.

Complexity Analysis
Performance

← → move through sections and cards