问题:给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为6的数组A{5， 6， 7， 1， 2， 8}，则其最长的单调递增子序列为{5，6，7，8}，长度为4.
分析:这里给出一种近乎求 所有的子单调序列的做法
这里的序列其实可以表示为一颗树来存储 如下图
故设计如下数据结构
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
public class Leaf
{
public int key = 0;
public List<Leaf> leafs = new List<Leaf>();
public Stack<int> stack = new Stack<int>();
private void OutTree(Leaf leaf)
{
if (leaf.leafs.Count <= 0)
{
Stack<int> sk = new Stack<int>();
foreach (var item in stack)
{
sk.Push(item);
}
foreach (var item in sk)
{
Console.Write(item + " ");
}
Console.WriteLine();
}
foreach (Leaf item in leaf.leafs)
{
stack.Push(item.key);
OutTree(item);
stack.Pop();
}
}
public void OutTree()
{
OutTree(this);
}
public void OutTree(List<Leaf> list)
{
foreach (var item in list)
{
OutTree(item);
}
}
}
}
这里有个输出树的算法 使用的是dfs回溯法，使用一个栈来保存父节点序列以方便输出
具体算法如下。 获取每个序列的开头 这些序列都是以逆序形式存在的发现了这个特点 可以求出每个的开头然后递归求出每个子序列的子序列的开头。。。构造树
代码如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
namespace ConsoleApplication1
{
class Program
{
//森林
static Dictionary<int, List<int>> dicNums = new Dictionary<int, List<int>>();
static void Main(string[] args)
{
List<int> nums = new List<int>() { 4,7,5,2,3,4,1,5,100,99,2,5,6,7,9,13,17};
Leaf tree = GetTree(nums);
for (int i = 0; i < tree.leafs.Count; i++)
{
dicNums.Add(tree.leafs[i].key, new List<int>());
}
tree.OutTree();
Console.Read();
}
static void OutPutTree(Leaf tree)
{
for (int i = 0; i < tree.leafs.Count; i++)
{
Console.Write(tree.leafs[i].key + " ");
OutPutTree(tree.leafs[i]);
}
}
//去掉最少的为单增就是单增
static Leaf GetTree(List<int> nums)
{
Leaf tree = new Leaf();
CreateTree(nums, tree);
return tree;
}
static void CreateTree(List<int> nums, Leaf tree)
{
//leaf的简单集
Dictionary<int, List<int>> dic = new Dictionary<int, List<int>>();
for (int i = 0; i < nums.Count; i++)
{
Leaf leaf = CreateLeaf(nums, tree, dic, i);
if (leaf != null)
{
tree.leafs.Add(leaf);
}
}
if (tree.leafs.Count <= 0)
{
return;
}
foreach (var item in tree.leafs)
{
CreateTree(dic[item.key], item);
}
}
private static Leaf CreateLeaf(List<int> nums, Leaf tree, Dictionary<int, List<int>> dic, int i)
{
bool flag = false;
//key代表第一个数字
foreach (Leaf item in tree.leafs)
{
if (nums[i] > item.key)
{
dic[item.key].Add(nums[i]);
//不存在新节点
flag = true;
}
}
if (flag)
{
return null;
}
if (!dic.ContainsKey(nums[i]))
{
//不存在num
Leaf leaf = new Leaf();
leaf.key = nums[i];
dic.Add(nums[i], new List<int>());
return leaf;
}
return null;
}
}
}
输出结果: