31251 Lec 5.2: Intro to Divide and Conquer

In this video we start looking at the algorithmic technique of divide and conquer. We illustrate the technique by looking at a divide and conquer approach to solving the Leetcode problem "Best time to buy and sell stock".

The basic idea of divide and conquer is to break down solving the original problem to solving smaller problems of the same kind. These smaller problems can then be solved recursively by applying the same algorithm.

In addition to solving the subproblems there are in general 3 kinds of additional work that need to be done in a divide and conquer algorithm, which we categorize as create/complete/combine.
1) Create the subproblems: Sometimes it is not obvious what the subproblems are, and the algorithm must do some preliminary work to construct the subproblems.
2) Complete: the solution to the subproblems may not be sufficient to answer the original problem. In this case we need to complete the picture by gathering some additional information. This is the case in the buy and sell stock problem.
3) Combine the solutions to the subproblems: sometimes we need to do further processing on the solutions to the subproblems in order to combine them into a solution to the original problem.

[holaamigoz]

what if u dont want the max profit of A[j]-A[i] but u want the tuple A[j], A[i] where the profit is max
?