2-7-2025

Maximum Continuous Sum

Consider this list:

$$[-3,5,1,-2,8,-3,0,1]$$

There are many contiguous sums: $-3+5+1=3$ $5+1+(-2)=4$

What’s the maximum contiguous sum we could get? In this case, $5+1+(-2)+8=12$

Use: if the values are, for example, stock changes (increase/decrease) then we’re asking for the maximum contiguous increase

Brute Force

Check all possible contiguous sums and take the max Pseudocode

max = A[0]
for i = 0 to n-1
	sum = 0
	for j = i to n-1
		sum = sum + A[j] # time C
		if sum > max     # |
			max = sum    # V
		end
	end
end

Time complexity is then ${\sum }_{i=0}^{n-1}{\sum }_{j=i}^{n-1}c=\cdots =\Theta (n^2)$

Divide & Conquer

Basic D&C methodology is to split the list into sublists (usually 2) and ask the same question about those sublists and combine the answers. For the sublists, do the same thing via recursion. Base case is generally a list of length 1. In this case, MCS(list of length 1) = that element. Idea: Given a list, split it

In addition, we’ll manually find the straddling max - the max which includes at least one element from each side of the split.