I am trying to solve every problem of Leetcode and write blogs to record it. Now I plan to read Introduction to Algorithms and solve problems match the book contents.

## What is Divide and conquer?

** Divide and conquer** is a method to solve a complex problem. When we think of a problem too complex or too big, we can try to divide the problem to some easy problems or small problems. Then we try to solve these small/easy problems and combine the results to solve the complex/big problem.

Divide and conquer is easy when you can easily find out how to divide a problem. But a lot of times how to divide a problem is hard. And different problem always needs a different divide approach. So if you want to master all divide and conquer problems you need to do a lot of practices. Only this way you can build a strong understanding of the thought of divide and conquer, and get more feeling of familiarity, and master more method to divide.

Chapter 2.3.1 of * Introduction to Algorithms* introduces

**, Chapter 4 “**

*Merge sort algorithm**” introduces*

**Divide and conquer****and**

*The maximum-subarray problem**.*

**Strassen’s algorithm for matrix multiplication**I implement these three algorithms from pseudocode from the book to Java code:

### Merge-Sort Java version：

GitHub address：https://github.com/tinyfool/leetcode/blob/master/src/CLRS/DivideAndConquer/MergeSort.java

### Maximum Subarray Java version：

GitHub address：https://github.com/tinyfool/leetcode/blob/master/src/CLRS/DivideAndConquer/MaximumSubarray.java

### Strassen’s algorithm for matrix multiplication Java version:

GitHub address：https://github.com/tinyfool/leetcode/blob/master/src/CLRS/DivideAndConquer/SquareMatrixMultiply.java

#### Brute fore

#### Simple recursive

**Helper functions**

**Matrix split and combine functions **

**Matrix add and minus functions**

**Strassen’s algorithm for matrix multiplication**

## LeetCode divide and conquer problems list

4 | Median of Two Sorted Arrays | Hard |

23 | Merge k Sorted Lists | Hard |

53 | Maximum Subarray | Easy |

169 | Majority Element | Easy |

215 | Kth Largest Element in an Array | Medium |

218 | The Skyline Problem | Hard |

240 | Search a 2D Matrix II | Medium |

241 | Different Ways to Add Parentheses | Medium |

282 | Expression Add Operators | Hard |

312 | Burst Balloons | Hard |

315 | Count of Smaller Numbers After Self | Hard |

327 | Count of Range Sum | Hard |

493 | Reverse Pairs | Hard |

514 | Freedom Trail | Hard |

426 | Convert Binary Search Tree to Sorted Doubly Linked List | Medium |

903 | Valid Permutations for DI Sequence | Hard |

932 | Beautiful Array | Medium |

973 | K Closest Points to Origin |