Maximum Sub-arrayProblem: You have an array of prices of a single product. Yo can buy only once and sell only once and calculate profit at the end. You know all the daily prices.
Solution: Instead of looking at daily prices look at daily change in price
Find-Maximum-Subarray(A, low, high)
If high == low
return ( low, high, A[low] )
else
mid = floor( (low + high)/2 )
(left-low, left-high, left-sum) = Find-Maximum-Subarray(A, low, mid)
(right-low, right-high, right-sum) = Find-Maximum-Subarray(A, mid+1,high)
(cross-low, cross-high, cross-sum) = Find-Max-Crossing-Subarray(A,low,mid,high)
if left-sum >= right-sum and left-sum >= cross-sum
return (left-low, left-high, left-sum)
elseif right-sum >= left-sum and right-sum >= cross-sum
return (right-low,right-high,right-sum)
else
return(cross-low,cross-high,cross-sum)
//------------------------------------------------------------------
Find-Max-Crossing-Subarray(A, low, mid, high)
left-sum = -inf
sum=0
for i = mid downto low
sum=sum +A[i]
if sum > left-sum
for j = mid +1 to high sum = sum + A[j]
if sum > right-sum
right-sum = sum
max-right = j
return (max-left; max-right; left-sum + right-sum) //========================
T(n) = Θ(1), if n = 1
T(n) = 2T(n/2) + Θ(n), if n > 1
//========================
T(n) = Θ(n lg n) SQUARE-MATRIX-MULTIPLY(A,B)
1 n = A.rows
2 let C be a new n x n matrix
3 for i = 1 to n
4 for j = 1 to n
5 c_ij = 0
6 for k = 1 to n
7 c_ij = c_ij + a_ik x b_kj
8 return C
Square Matrix Multiply Recursive (Divide and Conquer) Assume: n is a power of 2 subdivide A, B, and C into four n/2 x n/2 submatrices: A = | A_11 A_12 | B = | B_11 B_12 | C = | C_11 C_12 | | A_21 A_22 | | B_21 B_22 | | C_21 C_22 | then looking at the 4 submatrices of C = A * B C_11 = A_11 * B_11 + A_12 * B_21
C_12 = A_11 * B_12 + A_22 * B_22
C_21 = A_21 * B_11 + A_12 * B_21
C_22 = A_21 * B_12 + A_22 * B_22
MATRIX-MULTIPLY-RECURSE(A,B)
1 n = A.rows
2 let C be a new n x n matrix
3 if n == 1
4 c_11 = a_11 * b_11
5 else partition A, B, and C as 4 submatrices
6 C_11 = MATRIX-MULTIPLY-RECURSE(A_11,B_11) + MATRIX-MULTIPLY-RECURSE(A_12,B_21)
7 C_12 = MATRIX-MULTIPLY-RECURSE(A_11,B_12) + MATRIX-MULTIPLY-RECURSE(A_12,B_22)
8 C_21 = MATRIX-MULTIPLY-RECURSE(A_21,B_11) + MATRIX-MULTIPLY-RECURSE(A_22,B_21)
9 C_22 = MATRIX-MULTIPLY-RECURSE(A_21,B_12) + MATRIX-MULTIPLY-RECURSE(A_22,B_22)
10 return C
//==================================
there are 8 recursive calls to problems of size n/2, for 8T(n/2) time. There are also 4 matrix additions of (n/2)^2 entries for Theta(n^2) time. Thus:
T(n) = Θ(1) + 8T(n/2) + Θ(n^2)
= 8T(n/2) + Θ(n^2)
= Θ(n^3)
Consider multiplying two 2x2 matrices, as follows:
|A B| * |E F| = |AE+BG AF+BH|
|C D| |G H| |CE+DG CF+DH|
The obvious way to compute the right side is just to do the 8 multiplies and 4 additions. But imagine multiplies are a lot more expensive than additions, so we want to reduce the number of multiplications if at all possible. Strassen uses a trick to compute the right hand side with one less multiply and a lot more additions (and some subtractions).
Here are the 7 multiplies:
M1 = (A + D) * (E + H) = AE + AH + DE + DH
M2 = (A + B) * H = AH + BH
M3 = (C + D) * E = CE + DE
M4 = A * (F - H) = AF - AH
M5 = D * (G - E) = DG - DE
M6 = (C - A) * (E + F) = CE + CF - AE - AF
M7 = (B - D) * (G + H) = BG + BH - DG - DH
So to compute AE+BG, start with M1+M7 (which gets us the AE and BG terms), then add/subtract some of the other Ms until AE+BG is all we are left with. Miraculously, the M's are chosen so that M1+M7-M2+M5 works. Same with the other 3 results required.
|