300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.
For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

• 给出一个序列 $a_1, a_2, …, a_n$，求它的一个子序列（设为 $s_1, s_2, …, s_n$ ），使得这个子序列满足这样的性质：$ s_1 < s_2 < s_3 <…< s_n $ 并且这个子序列的长度最长，输出这个最长的长度。实际上，诸如最长下降子序列，最长不上升子序列等问题都可以看成同一个问题，仔细思考就会发现，这其实只是 $<$ 符号定义上的问题，并不影响问题的实质。

　　子序列和子字符串的不同之处在于，子序列不需要是原序列上连续的字符。对于 Longest Common Substring 以及 Longest Common Subsequence 这类题目，大多数需要用到 DP 的思想，其中，状态转移是关键。

二分图匹配问题

• 二分图
  
  • 顶点被分成两个不相交的集合（$U$ 和 $V$）并且同属一个集合内的点两两不相连（$E_{in U} = E_{in V} = \emptyset$），即要么没有圈，要么圈所包含的边数必定是偶数。
  • 二分图 的一个等价定义是：不含有 含奇数条边的环 的图。

　本文通过一道阿里面试题（下图），说说关于该题的字符串最长子串的查找问题。

　本文主要介绍 DFS 的 C++ 和 C 语言实现，并借助 LeetCode 上的一道题，说说基本的 DFS 在问题求解中的应用。

What’s D(epth)F(irst)S(earch)

　深度优先搜索算法（Depth First Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点 N 的所有边都己被探寻过，搜索将回溯到发现节点 N 的那条边的起始节点，这一过程一直进行到已发现从源节点可达的所有节点为止。
　如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

　本文记录了 Hexo 首页与归档博文排序如何自定义，想实现的功能是 index 按照修改日期排序，最近修改的文章置顶显示；Archives 归档则按照默认的创建时间前后排序。

　本文介绍几种常见的最短路径算法：

• Breadth-first Search 无权最短路径算法；
• Dijkstra 带权（非负权）图的单源最短路算法；
• Bellman-Ford 带权（可负权）图的单源最短路算法；
• Floyd-Warshall 带权（可负权）图的全源最短路算法，
  　包括它们各自的使用条件&范围，算法原理介绍以及代码实现。

[转发教程]
　　hexo系列教程：（一）hexo介绍 (获取安装文件 访问密码 2f87)。 可以通过阅读共享中的.txt笔记进行快速入门;

　本文介绍 Divide and Conquer（分而治之） 的一种典型算法，FFT（快速傅里叶变换）。

DFT

DFT：$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi k}{N} n}, k = 0, 1, 2, …, N-1$

• for each k: N complex mults, N-1 complex adds
• $e^{-j \frac{2 \pi k}{N} n}$ 预计算并保存在计算机中
• $O(N^2)$ computations for direct DFT $\Longrightarrow$ $O(N log_2 N)$ for FFT

• Consider the following game. A “dealer” produces a sequence $s_1, …, s_n$ of “cards”, face up, where each card $s_i$ has a value $v_i$. Then two players take turns picking a card from the sequence, but can only pick the first or the last card of the (remaining) sequence. The goal is to collect cards of largest total value. (For example, you can think of the cards as bills of different denominations.) Assume n is even.