CSE143 Complexity Example handout #8 // 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 = 0; } sum += list[i]; if (sum > max) { max = sum; maxStart = start; maxStop = i; } }
Stuart Reges