<![CDATA[
CSE143X Complexity Example handout #22
// This approach uses the brute force method of finding every possible
// starting and stopping index and adding up the values in that range.
// It has O(n^3) complexity. Assumes list.size > 0.
int max = list[0];
int maxStart = 0;
int maxStop = 0;
for (int start = 0; start < list.length; start++) {
for (int stop = start; stop < list.length; stop++) {
int sum = 0;
for (int i = start; i <= stop; i++) {
sum += list[i];
}
if (sum > max) {
max = sum;
maxStart = start;
maxStop = stop;
}
}
}
-------------------------------------------------------------------------------
// This approach improves on the brute force method by keeping partial sums
// instead of recomputing from scratch each time. It has O(n^2)
// complexity. Assumes list.size > 0.
int max = list[0];
int maxStart = 0;
int maxStop = 0;
for (int start = 0; start < list.length; start++) {
int sum = 0;
for (int stop = start; stop < list.length; stop++) {
sum += list[stop];
if (sum > max) {
max = sum;
maxStart = start;
maxStop = stop;
}
}
}
-------------------------------------------------------------------------------
// This approach keeps a running sum, resetting the starting point and
// resetting the sum to 0 if the sum ever goes negative. It has O(n)
// complexity. Assumes list.size > 0.
int max = list[0];
int maxStart = 0;
int maxStop = 0;
int start = 0;
int sum = 0;
for (int i = 0; i < list.length; i++) {
if (sum < 0) {
start = i;
sum = list[i];
} else {
sum += list[i];
}
if (sum > max) {
max = sum;
maxStart = start;
maxStop = i;
}
}
]]>