Guide to Competitive Programming

Examples
In this section we discuss two algorithm design problems that can be solved in several different ways. We start with simple brute force algorithms, and then create more efficient solutions by using various algorithm design ideas.

Given an array of n numbers, our first task is to calculate the maximum subarray sum, i.e., the largest possible sum of a sequence of consecutive values in the array. The problem is interesting when there may be negative values in the array. For example, shows an array and its maximum-sum subarray.

Maximum Subarray Sum

O(n3) Time Solution A straightforward way to solve the problem is to go through all possible subarrays, calculate the sum of values in each subarray and maintain the maximum sum. The following code implements this algorithm:

int best = 0;
for (int a = 0; a < n; a++) {
for (int b = a; b < n; b++) {
int sum = 0;
for (int k = a; k <= b; k++) {
sum += array[k];
}
best = max(best,sum);
}
}
cout << best << “\n”;

The variables a and b fix the first and last index of the subarray, and the sum of values is calculated to the variable sum. The variable best contains the maximum sum found during the search. The time complexity of the algorithm is O(n3), because it consists of three nested loops that go through the input.

O(n2) Time Solution It is easy to make the algorithm more efficient by removing one loop from it. This is possible by calculating the sum at the same time when the right end of the subarray moves. The result is the following code:

int best = 0;
for (int a = 0; a < n; a++) {
int sum = 0;
for (int b = a; b < n; b++) {
sum += array[b];
best = max(best,sum);
}
}
cout << best << “\n”;

After this change, the time complexity is O(n2).

O(n) Time Solution It turns out that it is possible to solve the problem in O(n) time, which means that just one loop is enough. The idea is to calculate, for each array position, the maximum sum of a subarray that ends at that position. After this, the answer to the problem is the maximum of those sums.

Consider the subproblem of finding the maximum-sum subarray that ends at position k. There are two possibilities:
1. The subarray only contains the element at position k.
2. The subarray consists of a subarray that ends at position k − 1, followed by the element at position k.

In the latter case, since wewant to find a subarray with maximum sum, the subarray that ends at position k − 1 should also have the maximum sum. Thus, we can solve the problem efficiently by calculating the maximum subarray sum for each ending position from left to right.

The following code implements the algorithm:

int best = 0, sum = 0;
for (int k = 0; k < n; k++) {
sum = max(array[k],sum+array[k]);
best = max(best,sum);
}
cout << best << “\n”;

The algorithm only contains one loop that goes through the input, so the time complexity is O(n). This is also the best possible time complexity, because any algorithm for the problem has to examine all array elements at least once.

Efficiency Comparison Howefficient are the above algorithms in practice? Table 3.2 shows the running times of the above algorithms for different values of n on amodern computer. In each test, the input was generated randomly, and the time needed for reading the input was not measured.

The comparison shows that all algorithms work quickly when the input size is small, but larger inputs bring out remarkable differences in the running times. The O(n3) algorithm becomes slow when n = 104, and the O(n2) algorithm becomes slow when n = 105. Only the O(n) algorithm is able to process even the largest inputs instantly.

Comparing running times of the maximum subarray sum algorithms