Expand your report to include the O(nlogn) solution. Follow the same format for reporting, including code, discussion, plots, and a table comparing the three algorithms.
To solve a problem of size n, recursively solve two subproblems of size approximately n/2, and combine their solutions to yield a solution to the complete problem. If we are able to do this with O(n) work to evaluate&combine the sub-solutions, then the total solution will be O(nlog). [T(1) = O(1) && T(n) = 2T(n/2)+O(n)]
The pattern recognition problem at hand operates on a vector of size n. We seek to divide this problem into two sub-problems by dividing the vector into two vectors of size n/2. We solve the problem for the subvectors and combine the solutions.
Our desire it to find the maximum-sum subvector. We can divide the vector into two sub vectors (a and b).
![]()
Then we find the maximum-sum subvectors in a and b which we will call ma and mb.
![]()
Finding ma and mb does not quite solve the entire problem, because the maximum-sum subvector could resided entirely in a ma, or entirely in b ma, or it could cross the border between a and b. We call mc the border crossing condition. So, we can solve the problem by recursively computing ma and mb and then find mc by some other method. We can observe that the left hand side of mc is the largest subvector that starts at the boundary and reaches into a, and the right hand side of mc is the largest subvector that starts at the boundary and reaches into b.
![]()
Consider the pseudo-code below
float maxsum(int [] x, int lower, int upper)
if (lower > upper) return 0 ; // zero elements O(1)
if (lower == upper) return max(0,x[lower]); // one element O(1)
middle = (lower + upper) / 2 ;
/* find lhs of mc */
lmax = sum = 0 ;
for (I= middle ; I>= lower;I--)
sum += x[I]
lmax = max(lmax,sum)
/* find rhs of mc */
rmax = sum = 0 ;
for (I= middle+1 ; I<=upper;I++)
sum += x[I]
lmax = max(lmax,sum)
return max(lmax+rmax, maxsum(x,lower,middle),maxsum(x,middle+1,upper)