第八十课最长不下降序列

 1 int search_max_path(Graph<int, int>& g, int v, Array<int>& count, Array<int>& path, Array<bool>& mark)
 2 {
 3     int ret = 0;
 4 
 5     int k = -1;
 6 
 7     SharedPointer< Array<int> > aj = g.getAdjacent(v);
 8 
 9     for(int i=0; i<aj->length(); i++)
10     {
11         int num = 0;
12 
13         if( !mark[(*aj)[i]] )
14         {
15             num = search_max_path(g, (*aj)[i], count, path, mark);
16         }
17         else
18         {
19             num = count[(*aj)[i]];
20         }
21 
22         if( ret < num )
23         {
24             ret = num;
25             k = (*aj)[i];
26         }
27     }
28 
29     ret++;
30 
31     count[v] = ret;
32     mark[v] = true;
33     path[v] = k;
34 
35     return ret;
36 }

程序如下：

  1 #include <iostream>
  2 #include "MatrixGraph.h"
  3 #include "ListGraph.h"
  4 
  5 using namespace std;
  6 using namespace DTLib;
  7 
  8 int search_max_path(Graph<int, int>& g, int v, Array<int>& count, Array<int>& path, Array<bool>& mark)
  9 {
 10     int ret = 0;
 11 
 12     int k = -1;
 13 
 14     SharedPointer< Array<int> > aj = g.getAdjacent(v);
 15 
 16     for(int i=0; i<aj->length(); i++)
 17     {
 18         int num = 0;
 19 
 20         if( !mark[(*aj)[i]] )
 21         {
 22             num = search_max_path(g, (*aj)[i], count, path, mark);
 23         }
 24         else
 25         {
 26             num = count[(*aj)[i]];
 27         }
 28 
 29         if( ret < num )
 30         {
 31             ret = num;
 32             k = (*aj)[i];
 33         }
 34     }
 35 
 36     ret++;
 37 
 38     count[v] = ret;
 39     mark[v] = true;
 40     path[v] = k;
 41 
 42     return ret;
 43 }
 44 
 45 SharedPointer< Graph<int, int> > create_graph(int* a, int len)
 46 {
 47     ListGraph<int, int>* ret = new ListGraph<int, int>(len);
 48 
 49     for(int i=0; i<len; i++)
 50     {
 51         ret->setVertex(i, a[i]);
 52     }
 53 
 54     for(int i=0; i<len; i++)
 55     {
 56         for(int j=i+1; j<len; j++)
 57         {
 58             if( a[i] <= a[j] )
 59             {
 60                 ret->setEdge(i, j, 1);
 61             }
 62         }
 63     }
 64 
 65     return ret;
 66 }
 67 
 68 void init_array(Array<int>& count, Array<int>& path, Array<bool>& mark)
 69 {
 70     for(int i=0; i<count.length(); i++)
 71     {
 72         count[i] = 0;
 73     }
 74 
 75     for(int i=0; i<path.length(); i++)
 76     {
 77         path[i] = -1;
 78     }
 79 
 80     for(int i=0; i<mark.length(); i++)
 81     {
 82         mark[i] = false;
 83     }
 84 }
 85 
 86 void print_max_path(Graph<int, int>& g, Array<int>& count, Array<int>& path)
 87 {
 88     int max = 0;
 89 
 90     for(int i=0; i<count.length(); i++)
 91     {
 92         if( max < count[i] )
 93         {
 94             max = count[i];
 95         }
 96     }
 97 
 98     cout << "Len : " << max << endl;
 99 
100     for(int i=0; i<count.length(); i++)
101     {
102         if( max == count[i] )
103         {
104             cout << "Element : " << g.getVertex(i) << " ";
105 
106             for(int j=path[i]; j != -1; j=path[j])
107             {
108                 cout << g.getVertex(j) << " ";
109             }
110 
111             cout << endl;
112         }
113     }
114 }
115 
116 void search_max_path(Graph<int, int>& g, Array<int>& count, Array<int>& path, Array<bool>& mark)
117 {
118     for(int i=0; i<g.vCount(); i++)
119     {
120         if( !mark[i] )
121         {
122             search_max_path(g, i, count, path, mark);
123         }
124     }
125 }
126 
127 void solution(int* a, int len)
128 {
129     DynamicArray<int> count(len);
130     DynamicArray<int> path(len);
131     DynamicArray<bool> mark(len);
132     SharedPointer< Graph<int, int> > g;
133 
134     g = create_graph(a, len);
135 
136     init_array(count, path, mark);
137 
138     search_max_path(*g, count, path, mark);
139 
140     print_max_path(*g, count, path);
141 }
142 
143 int main()
144 {
145     int a[] = {3, 18, 7, 14, 10, 12, 23, 41, 16,24};
146 
147     solution(a, sizeof(a) / sizeof(*a));
148 
149     return 0;
150 }

结果如下：

改变测试程序：

1 int main()
2 {
3     int a[] = {10, 30, 50, 1, 3, 5};
4 
5     solution(a, sizeof(a) / sizeof(*a));
6 
7     return 0;
8 }

结果如下；

上面的程序没有找到1,3,5这个序列，因此还有改进的余地。

  1 #include <iostream>
  2 #include "MatrixGraph.h"
  3 #include "ListGraph.h"
  4 
  5 using namespace std;
  6 using namespace DTLib;
  7 
  8 int search_max_path(Graph<int, int>& g, int v, Array<int>& count, Array<LinkList<int>*>& path, Array<bool>& mark)
  9 {
 10     int ret = 0;
 11 
 12     SharedPointer< Array<int> > aj = g.getAdjacent(v);
 13 
 14     for(int i=0; i<aj->length(); i++)
 15     {
 16         int num = 0;
 17 
 18         if( !mark[(*aj)[i]] )
 19         {
 20             num = search_max_path(g, (*aj)[i], count, path, mark);
 21         }
 22         else
 23         {
 24             num = count[(*aj)[i]];
 25         }
 26 
 27         if( ret < num )
 28         {
 29             ret = num;
 30         }
 31     }
 32 
 33     for(int i=0; i<aj->length(); i++)
 34     {
 35         if( ret == count[(*aj)[i]])
 36         {
 37             path[v]->insert((*aj)[i]);
 38         }
 39     }
 40 
 41     ret++;
 42 
 43     count[v] = ret;
 44     mark[v] = true;
 45 
 46     return ret;
 47 }
 48 
 49 SharedPointer< Graph<int, int> > create_graph(int* a, int len)
 50 {
 51     ListGraph<int, int>* ret = new ListGraph<int, int>(len);
 52 
 53     for(int i=0; i<len; i++)
 54     {
 55         ret->setVertex(i, a[i]);
 56     }
 57 
 58     for(int i=0; i<len; i++)
 59     {
 60         for(int j=i+1; j<len; j++)
 61         {
 62             if( a[i] <= a[j] )
 63             {
 64                 ret->setEdge(i, j, 1);
 65             }
 66         }
 67     }
 68 
 69     return ret;
 70 }
 71 
 72 void init_array(Array<int>& count, Array<LinkList<int>*>& path, Array<bool>& mark)
 73 {
 74     for(int i=0; i<count.length(); i++)
 75     {
 76         count[i] = 0;
 77     }
 78 
 79     for(int i=0; i<path.length(); i++)
 80     {
 81         path[i] = new LinkList<int>();
 82     }
 83 
 84     for(int i=0; i<mark.length(); i++)
 85     {
 86         mark[i] = false;
 87     }
 88 }
 89 
 90 void print_path(Graph<int, int>& g, int v, Array< LinkList<int>* >& path, LinkList<int>& cp)
 91 {
 92     cp.insert(v);
 93 
 94     if( path[v]->length() > 0 )
 95     {
 96         for(path[v]->move(0); !path[v]->end(); path[v]->next())
 97         {
 98             print_path(g, path[v]->current(), path, cp);
 99         }
100     }
101     else
102     {
103         cout << "Element : ";
104 
105         for(cp.move(0); !cp.end(); cp.next())
106         {
107             cout << g.getVertex(cp.current()) << " ";
108         }
109 
110         cout << endl;
111     }
112 
113     cp.remove(cp.length() - 1);
114 
115 
116 }
117 
118 void print_max_path(Graph<int, int>& g, Array<int>& count, Array< LinkList<int>* >& path)
119 {
120     int max = 0;
121     LinkList<int> cp;
122 
123     for(int i=0; i<count.length(); i++)
124     {
125         if( max < count[i] )
126         {
127             max = count[i];
128         }
129     }
130 
131     cout << "Len : " << max << endl;
132 
133     for(int i=0; i<count.length(); i++)
134     {
135         if( max == count[i] )
136         {
137             print_path(g, i, path, cp);
138 
139             cout << endl;
140         }
141     }
142 }
143 
144 void search_max_path(Graph<int, int>& g, Array<int>& count, Array<LinkList<int>*>& path, Array<bool>& mark)
145 {
146     for(int i=0; i<g.vCount(); i++)
147     {
148         if( !mark[i] )
149         {
150             search_max_path(g, i, count, path, mark);
151         }
152     }
153 }
154 
155 void solution(int* a, int len)
156 {
157     DynamicArray<int> count(len);
158     DynamicArray< LinkList<int>* > path(len);
159     DynamicArray<bool> mark(len);
160     SharedPointer< Graph<int, int> > g;
161 
162     g = create_graph(a, len);
163 
164     init_array(count, path, mark);
165 
166     search_max_path(*g, count, path, mark);
167 
168     print_max_path(*g, count, path);
169 }
170 
171 int main()
172 {
173     int a[] = {1, 3, 5, 4};
174 
175     solution(a, sizeof(a) / sizeof(*a));
176 
177     return 0;
178 }

结果如下：

第八十课 最长不下降序列

第八十课最长不下降序列