The Maximum Subarray Problem

Let us take another common problem in the world of computing and see various algorithms to solve it. Once again, we will start will a trivial or a "naive" method and then analyze and try to improve the efficiency of our algorithms.

INPUT :
A sequence of n real numbers (can be positive or negative)  which may indicate real-world numbers like stock prices over a period, or the business profit sheet of an individual over a period, where negative numbers indicate loss.
OUTPUT :
A smaller sequence from the original sequence wherein the numbers' sum is the maximum. This sequence may indicate the period wherein its most profitable to hold a stock as its value is the maximum or the period wherein the individual made the maximum profit. Since, practically, the sequence of numbers will be inputted as an array by the computer, we need to find the maximum non-empty contiguous subarray of that array.

1) THE TRIVIAL METHOD :
The trivial method is to traverse the entire array once and look for the difference in every combination-pair of the numbers. For an n-element array, the number of possible combinations will be ⁿC₂= n(n-1)/2. This takes ϴ(n²) asymptotically. (Recall that ϴ notation denotes asymptotically bound function between two functions c₁f(n) and c₂f(n), thus giving the "average case".) Also, the comparison of the various differences will take a constant amount of time, thus giving the trivial method a Ω(n²).

2) THE DIVIDE AND CONQUER METHOD :
The Divide and Conquer approach is a very common method in Computer Science problems. It works on 3 basic stages:

1. Divide
2. Solve/Conquer
3. Merge

Recursion is very widely used in divide-and-conquer approaches. Our divide-and-conquer algorithm works on the principle that an array can be divided into m (preferably equal) parts and then we can search each part-array for the maximum subarray. The combination of the maximum number of such contiguous part-subarrays will eventually merge into the required subarray. For our convenience, let us take m to be 2. Our algorithm has the following stages.

1. Recursively divide the array into 2 equal parts
2. Find the maximum subarray on the left half of the array
3. Find the maximum subarray on the right half of the array
4. Find the maximum subarray that "crosses over" the division i.e. that contains the point of division

Our pseudocode of the above algorithm accepts 3 parameters: The array A, a starting index "low", an ending index "high" and returns 3 parameters: a starting index lower, an ending index "higher" and the maximum sum "maxSum".

Algorithm findMaxSubarray(A, low, high)

1. if low == high then return (low, high, A[low])
2. mid = ⌊(low+high)/2⌋
3. (left-low, left-sum, left-high) = findMaxSubarray(A, low, mid)
4. (cross-low, cross-sum, cross-high) = findMaxCrossOverSubarray(A, low, mid, high)
5. (right-low, right-sum, right-high) = findMaxSubarray(A, mid, high)
6. if left-sum > cross-sum and left-sum > right-sum then return (left-low, left-sum, left-high)
7. else if right-sum > cross-sum and right-sum > left-sum then return (right-low, right-sum, right-high)
8. else return (cross-low, cross-sum, cross-high)

The subroutine "findMaxCrossOverSubarray" returns the maximum subarray that "crosses-over" the midpoint "mid". The pseudocode of this subroutine is:

Algorithm findMaxCrossOverSubarray(A, low, mid, high)

1. leftSum = rightSum = -∞
2. leftIndex = rightIndex = -∞
3. sum = 0
4. for i = mid downto low
5. sum += A[i]
6. if leftSum < sum then leftSum = sum, leftIndex = i
7. for j = mid upto high
8. sum += A[j]
9. if rightSum < sum then rightSum = sum, rightIndex = j
10. return (leftIndex, leftSum+rightSum, rightIndex)

It can be proved that the above pseudocodes take ϴ(n*log₂n), which is way better than the trivial method. The java version of the above pseudocodes is as follows:

NOTE :

As we are attempting to return more than one parameter from the function, we cannot do it in Java. Thus, we encapsulate all the 3 different entities into a user-defined data type (class). This introduces the overhead of instantiating the class objects and their handling. Thus, we see, that although the time asymptotically remains ϴ(n*log₂n), the overhead memory allocation increases in Java. In languages like Python where functions can return more than one variable, this overhead is avoided. This is a classic example of the constraints introduced during actual application of algorithms into languages.

KADANE'S ALGORITHM:
We end our discussion with the best possible algorithm for the problem stated. Kadane introduced an algorithm to solve the maximum subarray problem in O(n) since it is nothing but a for loop which is traversed n times. Kadane's algforithm is an implementation of "the two finger rule" which states that one finger is kept at the first index of the array and another finger is allowed to scan through the array finding the sum of the elements as it goes". The java program which implements Kadane's Algorithm is:

Evaluating a polynomial and Horner's Rule

Given the polynomial

where  are real numbers, we wish to evaluate the polynomial i.e. find it's value at a given value of x, say x₀. This value represents the value of p(x), which can be any function under analysis at the point x₀ in space.

INPUT :

1. The value of x₀
2. The values of the coefficients a₀...a_n

OUTPUT :

The value of the polynomial at x.


THE "NAIVE" METHOD :

The most basic and preliminary method would be to separately evaluate each term in the expression and then successively add all the terms (monomials). Let us consider p(x) to be a polynomial of degree n. It, then contains, at the most, n+1 terms (from degree 0 to n). The naive method, then, requires at the most n additions to add those n+1 terms. In fact, these n additions are absolutely necessary for any algorithm used.

Now lets consider the number of multiplications involved. An n-degree polynomial will have at the most n co-efficients. We need to perform 1 multiplication for each, giving us a total of n multiplications. This factor, too, is independent of the algorithm chosen. Additionally, when we calculate the powers of x, we multiply x by itself each time to get a higher power (we consider a machine where power calculation is NOT O(1), i.e. it cannot be performed in a single step, which is true in most cases). Therefore, to get xⁿ, we need to perform n multiplications. Therefore, maximum total number of multiplications for power will be:
                                                      ∑(i=0 to n-1) {i} = n(n-1)/2
i.e. (n²- n)/2 multiplications. But we can avoid the need to multiply n times to get xⁿ. We can use iterative methods to increase the efficiency, because xⁿ is x*x^n-1 and so on. Thus, by using iterative functions, we need only (n-1) multiplications.
Therefore, in the basic method, we need a total of n additions and (n²-n)/2 + n i.e. (n²+n)/2 multiplications, giving O(n²). However, in the iterative method, we need n - 1 + n = 2n - 1 multiplications along with n additions, still giving O(n). Can we do any better?

HORNER'S ALGORITHM :

Horner's algorithm provides a way of evaluating any polynomial in ϴ(n). It is just another way of representing every polynomial by iteratively multiplying the variable 'x' to a shorter sequence. Horner's method can be represented as follows:


The algorithm for Horner's method is pretty straightforward:

1.  y = 0                                         ϴ(1) 1 time
2.  for i = n downto 0                       ϴ(1) n+1 times
3. y = ai + x*y                                ϴ(1)                                     n times

Thus, the algorithm takes ϴ(n) which is way better than the naive method. Also, Horner's method takes n additions and n multiplications as can be seen from the algorithm above. Thus, it is more efficient i terms of space as well.

Horner's algorithm can be extended to find the "approximate roots" of the equation. If the Horner's equation above is observed, we find that each pair of parantheses enclose 1 polynomial smaller than p(x). Thus we can "break down" any given polynomial into smaller polynomials by dividing it by a given factor and subtracting it from a constant term. The constant term, thus becomes, the remainder and the constant factor, the divisor. For example,
                  x³ - 6x² + 11x - 6 can be represented in Horner's form as -6 + x (11 + x (-6 + x (1)))
When x-1 = 0; x = 1. This implies, that if we divide the above polynomial by (x-1), we can consider 1 to be a value of x. The above polynomial can, thus, be divided by (x-1) (here, the constant factor and divisor is 1) to get the quotient x² - 5x + 6 and remainder 0. This leads us to a very important format in Mathematics and in Computer Science: The Synthetic Division.

 x₀│   x³    x²    x¹    x⁰
 3 │   2    −6     2    −1
   │         6     0     6    
   └────────────────────────
       2     0     2     5

Notice the similarity between the algorithm mentioned above and the synthetic division performed here. The coefficient of x³ which is equivalent to a_n for n = 3 is directly copied and the later coefficients (a_n-1 to a₀) are multiplied by the value of x(i.e.3) to get the coefficients of a smaller polynomial (2x² + 0x + 2) and remainder 5. Thus, we see that by mere manipulation of coefficients as in the Horner's rule, we can not only evaluate any polynomial, but can also calculate the approximate roots of the same.