Mock interview January 13, 2017 -

dynamic programming discussion

Algorithm probelm discussion:
Find maximum number of chunks. 

[2, 1, 3, 5, 4] - N, number from 1 to N

break into chunks, sort each chunk, array is sorted. What is maximum number?

1, maximum 
[2, 1], [3], [5, 4] - maximum number is 3

[1, 2, 3, 4, 5]
sort [1,2 ,3, 4, 5]  1 maximum number is 1
[1], [2], [3], [4], [5] -> maximum number is 5

[3, 2, 1, 4, 5]  -> 3, [3, 2, 1], [4], [5]

first chunk - start 0 
end of first chunk 0, 1, .. n -1 - n option 
n 

length = 2
startIndex = 2
maximum chunk n 

first chunk -> 
0 
end - n option

1 shoud be in first chunk 
what else should be in the first chunk 

n * n = n^2 

2^(n-1)

your algorithm time complexity - 
How can you solve you?

2 + 3 + 4 + 5 = ?  ( start + end ) n / 2
14 
( 5 + 2 ) * 4 / 2 = 14

[ 2, 1, 3, 5, 4 ] [2 ,1] [3] [ 5, 4]

expected sum =  1 ( start + end ) n / 2
runningsum = 2
partition = 0

=============
expected sum = 3
runningSum =  3
parittion count = 1

extended algorithm - 
what if number of array is any number? Can you still come out linear soltuion?
left chunk maximum value compares to minimum value of right side of the array. 
Memoization
using array to store the 
[1 ,10, 3, 999, 50]   // extended algorithm - 
  ^
  
 [1] [10, 3, 999, 50]
 
 [10] [ 3, 999, 50]
 ...
 start   [             ]
         [             ]
         [             ]
         [             ] 
 
 maxpart
 Dp[i,j] = 1 + max(Dp[a, b]) | a > i; b > j; b > a
 
 [50]
 
 [999, 50]
 
 [3, 999, 50]
 
 [3, 999] [50] XXX
  
 [3, 999, 50] ///  [3, 999] [50] XXX ||  [3] [999, 50] 
 
 [10, 3, 999, 50]
 
 preprocess the array, store to extra array
from right to left iterate the array, store minimum value 

[1, 10, 3, 999, 50]

right to left/ min value array [1,3,   3,  50, 50]
left to right max value array  [1,10, 10, 999, 999]
                               [T,F,  F,  F,   F], 2 chunks
                               
Ask dynamic programming formula:
dp[i] = 1 + (RtoL[i] < LtoR[i]) ? 1 : 0