Divde and Conquer

Question 1

Finding Max SubArray

Answer 1

=> Divide the array into 3 elements: Mid, Left, Right
=> Create 2 for loops
=> Left for loop starts from mid-1 and go until 0, and find best sum of left elements;
=> Right for loop starts from mid+1 and go until end, and find the best sum of right elements;
=> at the end, get the bestcombinedSum by combining localMaxOfLeft + mid + LocalMaxOfRight
=> find the best subarray possible by recursively calling itself passing 0, mid-1 && mid+1, end
=> compare 3 values and get a max out of 3
return Math.max(bestCombinedSum, Math.max(leftHalf, rightHalf));

Question 2

Definition of Dynamic Programming

Answer 2

method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure (array, map, etc.). So the next time the same sub-problem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time.