Kadane and subarray problems in Python

Why it matters

"Find the maximum subarray sum" is one of the most asked list questions in technical interviews. It looks easy when you read it, and the first solution most people write is slow. Kadane's algorithm solves it in one pass, using a single running number, and the same way of thinking solves a whole family of related questions. This lesson builds the idea from zero, then applies it to stock prices, products and circular lists.

First principles: what a subarray is

A subarray is a continuous slice of a list, with no gaps. Think of a paper strip cut out of a longer strip. You can cut any piece, as long as the piece is one unbroken run. For the list [1, 2, 3], the subarrays are [1], [2], [3], [1, 2], [2, 3] and [1, 2, 3]. The piece [1, 3] is not a subarray, because the value 2 sits between the 1 and the 3, and a subarray cannot skip it.

A subarray is named by two indexes. It starts at index i and ends at index j, and it includes both ends. In Python, the slice a[i:j + 1] is that subarray. The number of subarrays of a list of length n is n times n + 1 divided by 2. For n = 3, that is 6, which matches the list above. The count grows quickly: a list of 1,000 values has about 500,000 subarrays.

The question "what is the largest sum of a subarray?" asks you to choose the best of those many slices. Trying each one is the brute-force method.

The brute-force method and why it is slow

The simplest correct program tries every start index and every end index, adds the values in between, and keeps the largest total.

a = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
best = a[0]
n = len(a)
for i in range(n):
    for j in range(i, n):
        total = 0
        for k in range(i, j + 1):
            total += a[k]
        best = max(best, total)

This has three loops, one inside the other, so it does about n cubed divided by 6 additions. For 1,000 values, that is about 170 million additions. You can improve it to n squared by keeping the running sum from i as j moves forward, instead of re-adding from scratch. That is still too slow for large inputs, and an interviewer will expect you to see a better way.

Python makes the slow version look shorter, because sum(a[i:j + 1]) adds a slice in one call. The call still does the same work inside, so the cost is the same. Shorter code does not mean a faster method.

The key idea: the best slice that ends here

Kadane's idea is to stop asking about all slices at once. Instead, walk through the list once, and at each position ask: what is the best subarray that ends exactly at this position? Call that value current.

At each new value a[i] you have two choices. You can extend the previous slice by adding a[i] to it. Or you can start a brand-new slice that begins at a[i]. Whichever gives the bigger total is the new current. The formula is:

current = max(a[i], current + a[i])
best    = max(best, current)

The first line makes the choice. The second line keeps the overall answer, because the best slice overall must end at some position, and current has been tracking the best slice ending at every position.

The backpack picture

Imagine you carry a backpack on a walk. Each step, you pick up a coin with a value, which may be negative because you also pay out a fee. Your backpack's total is your running sum. If the backpack total is below zero, it only drags you down: any slice that starts with it is worse than a slice that starts fresh at the next coin. So you empty the backpack and start again. If the total is zero or above, carrying it forward can only help or do nothing, so you keep it.

The formula max(a[i], current + a[i]) is exactly that decision. If current + a[i] is smaller than a[i] alone, it means current was negative, and you drop it. That is the moment you start a new slice.

Worked example 1: all negative values

The formula has a subtle requirement. You must start current and best with a real value from the list, not with 0. Here is the reason. Suppose every value is negative, such as [-3, -1, -2]. A subarray must contain at least one value, so the best answer is the least negative single value, which is -1. If you start best at 0, the program will claim the answer is 0, and 0 is not the sum of any subarray.

The program below shows this. It defines the function max_subarray that you will build on through the lesson.

Output:

-1
6

Trace the first call. current and best both start at -3. For a[1] = -1, the choice is between -1 alone and -3 + -1 = -4. The larger is -1, so current becomes -1 and best becomes -1. For a[2] = -2, the choice is -2 alone or -1 + -2 = -3. The larger is -2, so current becomes -2, but best stays -1. The output is -1.

The second call is the classic example. The table below traces current and best for each value. Read it from top to bottom, one row per index.

The final best is 6. It came from the slice that starts at index 3 and ends at index 6, which is 4, -1, 2, 1. Notice that the program never built that slice. It only kept the running numbers.

This is the main idea behind Kadane's algorithm, and it is a good way to think about many list problems. The answer depends on a small summary of everything seen so far, not on the whole history. Here the summary is the best slice ending at the current position. If you can name the summary for your problem, the program is usually short. If you cannot, the problem probably needs a different summary, such as the lowest price so far in the stock problem, or the prefix counts in the subarray-sum problem.

Worked example 2: returning the indexes of the best slice

Often the question asks for the slice itself, or for its start and end positions. You need one extra idea. Remember the index where current last restarted. That is the start of the current slice. When best improves, copy the start and the current index.

The rule for restarting is: if current is negative before adding the new value, start fresh. This is the same as the formula, because current + a[i] is less than a[i] exactly when current is negative.

Save the program as main.py. Run it with python3 main.py, then type 9 and press Enter, then type -2 1 -3 4 -1 2 1 -5 4 and press Enter.

n = int(input())
a = [int(x) for x in input().split()]
 
current = a[0]
start = 0
best = a[0]
best_start = 0
best_end = 0
for i in range(1, n):
    if current < 0:
        current = a[i]
        start = i
    else:
        current += a[i]
    if current > best:
        best = current
        best_start = start
        best_end = i
print(f"Best sum {best} from index {best_start} to {best_end}")

Output:

Best sum 6 from index 3 to 6

The start variable only changes when current restarts. For this input it changes at index 1, at index 3, and never again until the end. The best value is first reached at index 6, when the slice from index 3 holds 4, -1, 2 and 1. Later values do not beat 6, so the answer stays.

The line f"Best sum {best} ..." is an f-string. The f before the quote lets the text hold names in braces, and Python puts each value in place. It is the usual way to build a line of output in Python.

Notice the if current < 0 test. It makes the restart decision with a plain comparison, which many learners find easier to read than the max form. Both give the same answer. The difference is only in how the decision is written.

Worked example 3: the best time to buy and sell

A famous question is about a price history. You may buy once and sell once later, and you want the largest profit. Notice that it is a subarray problem in disguise. The profit from buying on day i and selling on day j is prices[j] - prices[i]. If you look at the day-to-day changes, the profit is the best slice of changes, but the direct version is simpler.

Walk through the prices once. Keep the lowest price seen so far, which is the best day to have bought. At each day, the best profit that ends by selling today is today's price minus that lowest price. Keep the largest such profit.

Save the program as main.py and type 6, then 7 1 5 3 6 4.

n = int(input())
prices = [int(x) for x in input().split()]
if n == 0:
    print(0)
else:
    lowest = prices[0]
    profit = 0
    for i in range(1, n):
        profit = max(profit, prices[i] - lowest)
        lowest = min(lowest, prices[i])
    print(profit)

Output:

5

Trace it on 7 1 5 3 6 4. The lowest starts at 7. On day 1 the price is 1: the profit from selling is 1 - 7, which is negative, so profit stays 0, and the lowest becomes 1. On day 2 the price is 5: the profit is 5 - 1 = 4, so profit becomes 4. On day 3 the price is 3: the profit is 3 - 1 = 2, which is not better. On day 4 the price is 6: the profit is 6 - 1 = 5, so profit becomes 5. On day 5 the price is 4: the profit is 3, not better. The answer is 5, from buying on day 1 at price 1 and selling on day 4 at price 6.

Why does profit start at 0 and not at a negative number? Because doing nothing is always allowed. If prices only fall, the best you can do is not trade, and the answer is 0. A run with 4 and 9 7 4 3 prints 0. Check that in your head before you run it.

Why does the program compare against the lowest price before the day's update? Because you cannot buy and sell on the same day and gain anything. Selling today at today's price needs an earlier, lower price, so the comparison must use the lowest price from days before today. Updating lowest after the comparison makes this happen.

This is O(n) time and O(1) space. It is also a pattern: "best difference where the smaller value comes first" appears in many interview questions.

Worked example 4: the maximum product subarray

Kadane's idea works for products too, but with one new trap. Two negative numbers multiply to a positive. So a very negative running product can become the best product after one more negative value. For example, in [2, -5, -2, -4, 3], the answer is -2 * -4 * 3 = 24, but the running product of the first three values is 2 * -5 * -2 = 20, and a single negative value flips the sign again.

The fix is to track two numbers at each position: the largest product of a subarray ending here, and the smallest. The smallest matters because a negative value times the smallest product gives the largest product. At each new value, compute the two candidates, max_end * a[i] and min_end * a[i], and also consider the value alone. The new largest is the biggest of the three, and the new smallest is the smallest of the three.

Save the program as main.py and type 5, then 2 -5 -2 -4 3.

n = int(input())
a = [int(x) for x in input().split()]
 
max_end = a[0]
min_end = a[0]
best = a[0]
for i in range(1, n):
    cand_a = max_end * a[i]
    cand_b = min_end * a[i]
    max_end = max(a[i], cand_a, cand_b)
    min_end = min(a[i], cand_a, cand_b)
    best = max(best, max_end)
print(best)

Output:

24

Trace it. Start with max_end = min_end = best = 2. For -5, the two candidates are 2 * -5 = -10 in both cases. So max_end is the largest of -5, -10, -10, which is -5, and min_end is -10. The best stays 2.

For -2, the candidates are max_end * -2 = 10 and min_end * -2 = 20. The new max_end is 20, from the slice 2, -5, -2. The new min_end is -2. The best becomes 20.

For -4, the candidates are 20 * -4 = -80 and -2 * -4 = 8. The new max_end is 8, from the slice -2, -4, and the best stays 20.

For 3, the candidates are 8 * 3 = 24 and -80 * 3 = -240. The new max_end is 24, from -2, -4, 3. The best becomes 24.

Python's max and min take any number of arguments, so max(a[i], cand_a, cand_b) reads cleanly. Python integers never overflow, so the products need no special type. In a language with 32-bit integers, two values near one million would multiply past the limit, and the result would be wrong.

The answer for [2, 3, -2, 4] is 6, from 2 * 3. Try it to check that you can follow the two-number tracking. If you keep only the largest product, the negative values break the chain, and the answer for [2, -5, -2, -4, 3] is no longer 24.

Worked example 5: the maximum circular subarray

A circular list joins its two ends, so the last value is next to the first. A slice can wrap around. For [5, -3, 5, -2, 4], the slice 4, 5, -3, 5, reading from the end and wrapping to the start, is a valid circular slice. Kadane alone misses it, because a normal subarray cannot wrap.

The trick is to notice that a wrapping slice is the whole list with one middle piece removed. So a wrapping slice's sum is total - (sum of a middle slice). To make the wrapping sum as large as possible, remove the most negative middle slice. The minimum subarray sum is found with the same Kadane pattern, but using min in place of max.

So the answer is the larger of two numbers. The first is the ordinary maximum subarray. The second is the total minus the minimum subarray. One exception applies. If every value is negative, total - minimum would remove everything and give 0, which is not a valid answer, because a slice must have at least one value. In that case, the answer is just the ordinary maximum.

Save the program as main.py and type 5, then 5 -3 5 -2 4.

n = int(input())
a = [int(x) for x in input().split()]
 
total = a[0]
cur_max = a[0]
best_max = a[0]
cur_min = a[0]
best_min = a[0]
for i in range(1, n):
    total += a[i]
    cur_max = max(a[i], cur_max + a[i])
    best_max = max(best_max, cur_max)
    cur_min = min(a[i], cur_min + a[i])
    best_min = min(best_min, cur_min)
 
answer = best_max
if best_max >= 0:
    answer = max(best_max, total - best_min)
print(answer)

Output:

12

Trace the numbers. The total of 5, -3, 5, -2, 4 is 9. The ordinary maximum subarray is 9 itself, because the whole list sums to 9 and no better slice exists. The minimum subarray is -3, the single value. The wrapping option is total - best_min = 9 - (-3) = 12. That is the slice made by everything except the -3: 5, -2, 4, 5, which wraps from the end back to the start. The answer is 12, the larger of 9 and 12.

If you run the same input with all values negative, such as -3 -1 -2, the program prints -1, not 0. The check best_max >= 0 sends that case straight to best_max.

Why Kadane is correct

A method is only useful if you can prove it, so here is a short argument for Kadane's rule.

Define ending[i] as the largest sum of any subarray that ends exactly at position i. The answer to the whole problem is the largest of all the ending values, because every subarray ends somewhere. So the question is how to compute each ending[i] quickly.

A subarray that ends at i is one of two kinds. Either it has one element, a[i] itself, or it has more than one element. A subarray with more than one element is a subarray that ends at i - 1, with a[i] added to its end. So the best subarray of the second kind has sum ending[i - 1] + a[i].

That gives the rule. ending[i] is the larger of a[i] and ending[i - 1] + a[i]. This is exactly the formula current = max(a[i], current + a[i]), because current holds ending[i - 1] at the start of step i. Since best keeps the largest current seen so far, it holds the largest ending value, which is the answer.

The rule also explains the restart. The second option wins exactly when ending[i - 1] is negative, because then ending[i - 1] + a[i] is smaller than a[i]. A negative prefix can never help a later subarray, because dropping it always gives a bigger sum. That is the backpack argument from earlier, written as a rule about numbers.

Three approaches compared

Kadane is not the only method, and an interviewer may ask why you chose it. The table below compares the main approaches for the maximum subarray sum and the related counting problem.

The difference is large in practice. With n equal to 100,000, the first method needs on the order of 10 to the power 15 steps, which no judge will wait for. The second needs on the order of 10 to the power 10, which is still too slow for most limits. The last two need about 100,000 steps, which finishes in a fraction of a second. Choosing the method is therefore part of the answer, not a detail.

Related problems and their patterns

Once you see Kadane as "the best slice ending here, updated one value at a time", the related problems follow.

The last row connects to the next lesson. A grid can be turned into a column-sum list for each pair of rows, and Kadane runs on each one. That gives O(rows squared times columns) time, which is the standard answer for the 2D version.

A variation: stock with a transaction fee

Suppose each sale costs a fee f, paid when you sell. A trade is now worth doing only when the rise is bigger than the fee. The lowest-price trick from worked example 3 is no longer enough on its own, because the best plan may depend on earlier trades. The clean method keeps two running values for each day. cash is the best profit when you hold no share at the end of the day. hold is the best value when you hold one share, counted as profit so far minus the price you paid for that share.

Each day updates both values, in this order. A sale turns a held share into cash, so cash becomes the larger of its old value and hold + price - fee. A purchase turns cash into a held share, so hold becomes the larger of its old value and cash - price. Start with cash = 0 and hold = -prices[0]. The answer is cash after the last day.

Test it on the prices 1 3 2 8 4 9 with fee 2. The best plan buys at 1 and sells at 8, which is a profit of 8 - 1 - 2 = 5. Then it buys at 4 and sells at 9, which is a profit of 9 - 4 - 2 = 3. The total is 8. A plan that buys at 1 and sells only at 9 earns 6, which is less. Running the two-value loop on these prices, with cash = 0, hold = -prices[0] and the fee of 2, gives 8. The loop does one pass and keeps two numbers, so it runs in O(n) time and O(1) space. Compare this with the simple profit loop: the extra value hold is what lets a later purchase reuse the cash from an earlier sale.

Common mistakes

1. Starting best at 0. With the list [-3, -1, -2], a best of 0 is returned, and the correct answer is -1. Always start from a[0], or from the first real value.

2. Forgetting an empty list. a[0] on an empty list raises IndexError: list index out of range. Decide what an empty list should return, and check for it first with if not a:.

3. Confusing a subarray with a subsequence. A subsequence may skip values. For [1, 2, 3], the subsequence 1, 3 is allowed, but the subarray 1, 3 is not. Kadane is only correct for subarrays.

4. Returning the sum when the question asks for indexes. Worked example 2 shows the fix: remember where current last restarted, and copy the indexes when best improves.

5. Using one number for products. For the product version, tracking only the largest product fails once a negative value appears. Track the smallest too.

6. Using a 32-bit limit in other languages. Python integers do not overflow, so this mistake does not happen in Python. It does happen in Java and C++ solutions of the same problem, where two values near 100,000 multiply to 10 billion, which does not fit in a 32-bit int. Read the Java lesson on this topic if you work in those languages.

7. Starting the profit at the first difference. Some learners start profit at prices[1] - prices[0]. For [9, 7] that gives -2, but doing nothing is allowed, so the answer is 0. Start profit at 0.

Debugging walkthrough: the answer is 0 when every value is negative

A teammate writes this code and reports a bug.

Output:

0
0

The bug shows on [-3, -1, -2]. The program returns 0. Work through it. The value 0 is not in the list, so the program cannot have found a real subarray with sum 0. The cause must be the starting value of best. best starts at 0, and max(best, current) never drops below 0, so once best is 0, it stays 0. The fix is to start both current and best at a[0], and loop from index 1.

The check to run after any fix is a case with all negative values, and a case with a single value. For [-7], the right answer is -7. The old code returns 0, and the fixed code returns -7. Those two checks catch the bug immediately, and they are the first two tests you should write for any Kadane solution.

Variations and edge cases

Single element. [5] should return 5. A loop that starts at index 1 does nothing, and the start values carry the answer.

All zeros. [0, 0, 0] should return 0. This is a valid answer, because the subarray 0 has sum 0.

All positive. The whole list is the answer, because every extension increases the sum. Kadane handles this without any special case.

Large values. Python handles any size of whole number, so the sum never wraps around. Very large numbers still take more time to add, but the result is exact.

Ties. When two slices have the same best sum, the usual answer is any of them, unless the problem asks for the longest or the first. Read the question for that rule before you choose > or >= in the update.

Interview-style questions

"What is the time complexity of Kadane's algorithm?" O(n). Each value is visited once, and each visit does a constant amount of work. The space is O(1), because only a few variables are kept.

"Why does Kadane work?" Because the best slice ending at position i is either the best slice ending at i - 1 extended by a[i], or a[i] alone. The algorithm keeps the better of the two at every step, so it never misses the best overall slice.

"What changes if the answer must be at least k values long?" The restart rule no longer works directly. You need a prefix-sum table and a minimum over a window of earlier prefixes. This is a good follow-up to show you can reason about changing constraints.

"How do you handle the product version?" Track both the largest and the smallest product ending at each position, because a negative value swaps which one is larger.

"What if the values arrive one at a time and you cannot store them?" Kadane is the right answer. It keeps only current and best, so the extra memory is O(1), and each value is handled as it arrives. A prefix-sum method would need to store the whole list first.

"What if the question asks for the best subarray of every length from 1 to n?" That is harder than the single maximum. A direct answer loops over every length and every start, which is O(n squared). Say so, and say that you would look for a faster method only if the constraints required it.

"What if every value is positive?" Then the whole list is the answer, because every value adds to the total. Kadane gives that result, and the interviewer may ask you to say so first, to show you understood the structure.

"Why not sort the values first?" Sorting throws away the order, and a subarray depends on order. Sorting costs O(n log n) time and answers a different question, such as the largest k values.

A strong answer names the cost and the reason the method is correct, and it covers the all-negative case without being asked.

Real-world uses

Kadane's idea appears in finance, where it finds the best period for an investment with daily gains and losses. It appears in signal processing, when a program looks for the strongest stretch of a noisy signal. It appears in image processing, in the two-dimensional version used to find the brightest rectangle in a picture. And it appears in any system that tracks a running score and needs the best recent stretch, such as the best run of wins in a sports log.

Practice

Try each one before you read the answer. Save each program as main.py and run it with python3 main.py.

1. Run Kadane by hand on [5, -9, 6, -2, 3]. Write down the value of current after each index. The final best is 7, from the slice 6, -2, 3.

Show the answer

Start with current = 5. Index 1, value -9: max(-9, 5 - 9 = -4) is -4. Index 2, value 6: max(6, -4 + 6 = 2) is 6, so it restarts. Index 3, value -2: max(-2, 6 - 2 = 4) is 4. Index 4, value 3: max(3, 4 + 3 = 7) is 7. The current values are 5, -4, 6, 4, 7. The best is 7.

2. Change worked example 2 so the list is written in the program, and it prints the start and end indexes of the best slice. The output must show indexes 3 to 6 for [-2, 1, -3, 4, -1, 2, 1, -5, 4].

Show the answer

Output:

Best sum 6 from index 3 to 6

3. Find the stock profit for [9, 7, 4, 3]. What should it be, and why?

Show the answer

The answer is 0. The price falls every day, so every sale is at a lower price than every earlier buy, and the best you can do is not trade. The program starts profit at 0 and never raises it, because every prices[i] - lowest is negative.

4. Given [-1, -4, 3], what does the maximum subarray sum return? What does a naive "start at 0" version return? Explain the difference in one sentence.

Show the answer

The correct answer is 3, from the single value 3. Kadane starting at a[0] gets there: current is -1, then max(-4, -5) gives -4, then max(3, -1) gives 3. The naive version starting best at 0 also returns 3 here, because 3 is positive. The difference only shows when every value is negative, such as [-1, -4], where the correct answer is -1 and the naive version returns 0.

5. Find the maximum product subarray for [-2, 0, -1]. Predict the answer, then check with the program from worked example 4 on this input.

Show the answer

The answer is 0. Any slice that includes the zero has product 0, and the single -2 and -1 are worse. Input 3, then -2 0 -1, with the program from worked example 4, prints 0. The zero resets both the largest and the smallest product, because 0 * anything is 0, and the candidate for the new value alone, which is -1, is smaller than 0.

6. Find the longest subarray with sum exactly 0 in [1, -1, 2, -2, 3]. Hint: prefix sums. Write the prefix values, and find the longest pair of equal prefix values. The answer is 4, from index 0 to 3.

Show the answer

The prefix values are 0, 1, 0, 2, 0, 3. The value 0 appears at positions 0, 2 and 4. The longest gap is between positions 0 and 4, which is the subarray from index 0 to 3, length 4: 1, -1, 2, -2, which sums to 0. Checking the sum: 1 - 1 + 2 - 2 = 0. Storing the first position of each prefix value in a dict gives this in one pass.

Output:

4

7. Write a program that reads prices and prints the largest profit from at most two buy-and-sell trades. You must sell before you buy again. Input 8, then 3 3 5 0 0 3 1 4. The answer is 6: buy at 0 and sell at 3, then buy at 1 and sell at 4.

Show the answer

n = int(input())
p = [int(x) for x in input().split()]
 
buy1 = float("inf")
sell1 = 0
buy2 = float("inf")
sell2 = 0
for price in p:
    buy1 = min(buy1, price)
    sell1 = max(sell1, price - buy1)
    buy2 = min(buy2, price - sell1)
    sell2 = max(sell2, price - buy2)
print(sell2)

The four variables are buy1, the lowest price so far; sell1, the best profit after one trade; buy2, the lowest effective cost of a second buy, which is the price minus the profit already made; and sell2, the best profit after two trades. Each step updates them in that order, so a second trade can reuse the first trade's profit. The value float("inf") stands for infinity, a number bigger than any price, so the first min always takes the real price.

8. Find the maximum circular subarray sum for [-3, -1, -2]. The answer is -1. Explain why the total minus the minimum would give a wrong answer here, using the exception from the lesson.

Show the answer

The total is -6 and the minimum subarray is -6 itself (the whole list), so total - min is 0. That 0 would mean "remove everything", which is an empty slice and not allowed. The rule is that when every value is negative, the answer is just the ordinary maximum, -1. The program in worked example 5 handles this with the check best_max >= 0.

9. Explain in one paragraph why Kadane does not need to check every start index. Use the backpack picture.

Show the answer

Once the running total in the backpack is negative, any slice that carries it forward is worse than a slice that starts at the next value. So the algorithm never needs to remember the older starts, because it already knows the best slice that ends at each position. The backpack is emptied at exactly the moments where a longer slice cannot win.

10. Write a program for the "longest subarray where all values are positive" version: given values that are all positive and a target k, print the length of the longest subarray with sum at most k. Use a sliding window with two indexes. Input 5, then 1 2 3 4 5, then 9. The answer is 3 (2 3 4).

Show the answer

n = int(input())
a = [int(x) for x in input().split()]
k = int(input())
 
left = 0
total = 0
best = 0
for right in range(n):
    total += a[right]
    while total > k and left <= right:
        total -= a[left]
        left += 1
    best = max(best, right - left + 1)
print(best)

The window grows to 1 2 3 (sum 6), then 1 2 3 4 (sum 10, too big), so left moves and the window becomes 2 3 4 (sum 9). The best length is 3. The window only works because all values are positive: shrinking from the left always lowers the sum.

What you now know

• A subarray is a continuous slice, and a brute-force search over all slices is O(n cubed) or O(n squared).
• Kadane's algorithm tracks the best slice ending at each position, using current = max(a[i], current + a[i]), and runs in O(n) time and O(1) space.
• Start current and best from a real value, not 0, so all-negative inputs are correct.
• To return the indexes, remember where current last restarted.
• For products, track the largest and the smallest product ending at each position.
• For circular lists, the answer is the larger of the ordinary maximum and the total minus the minimum, except when every value is negative.
• The stock problem is a "lowest so far, best difference" scan, and a prefix sum with a dict solves a subarray sum with negative values.