运行时间以及一维数组和二维数组运行时间对比

看如下代码：（三个一维）

 1 #include <iostream>
 2 #include <string>
 3 #include <string.h>
 4 #include <vector>
 5 #include <time.h>
 6 using namespace std;
 7 long MAX=1010;
 8 int a[1000];
 9 int maxa[1000];
10 int pos[1000];
11 int main() {
12     clock_t start = clock();
13     int N;
14     cin >> N;
15     for (int i = 1; i <= N; ++i) {
16         cin >> a[i];
17         maxa[i] = 1;
18     }
19     int maxfinal = 0;
20     int final_pos = 0;
21     for (int k = 2; k <= N; ++k) {
22         for (int i = k - 1; i >= 1; --i) {
23             int data;
24             if (a[k] > a[i]) {
25                 if (maxa[k] < maxa[i] + 1) {
26                     maxa[k] = maxa[i] + 1;
27                     pos[k] = i;
28                     if (maxa[k] > maxfinal) {
29                         maxfinal = maxa[k];
30                         final_pos = k;
31                     }
32                 }
33 
34             }
35         }
36     }
37     cout << maxfinal << endl;
38     for (int j = final_pos;;) {
39         if (a[j] == 0)
40             break;
41         cout << a[j] << " ";
42         j = pos[j];
43 
44 
45     }
46 
47     clock_t ends = clock();
48     cout << "Running Time : " << (double) (ends - start) / CLOCKS_PER_SEC << endl;
49 
50 
51 }

一个二维：

 1 #include <iostream>
 2 #include <string>
 3 #include <string.h>
 4 #include <vector>
 5 #include <time.h>
 6 using namespace std;
 7 long MAX=1010;
 8 int a[1000][3];
 9 
10 int pos[1000];
11 int main() {
12     clock_t start = clock();
13     int N;
14     cin >> N;
15     for (int i = 1; i <= N; ++i) {
16         cin >> a[i][1];
17         a[i][2] = 1;
18     }
19     int maxfinal = 0;
20     int final_pos = 0;
21     for (int k = 2; k <= N; ++k) {
22         for (int i = k - 1; i >= 1; --i) {
23             int data;
24             if (a[k][1] > a[i][1]) {
25                 if (a[k][2] < a[i][2] + 1) {
26                     a[k][2] = a[i][2] + 1;
27                     a[k][3] = i;
28                     if (a[k][2] > maxfinal) {
29                         maxfinal = a[k][2];
30                         final_pos = k;
31                     }
32                 }
33 
34             }
35         }
36     }
37     cout << maxfinal << endl;
38     for (int j = final_pos;;) {
39         if (a[j][1] == 0)
40             break;
41         cout << a[j][1] << " ";
42         j = a[j][3];
43 
44 
45     }
46     clock_t ends = clock();
47     cout << "Running Time : " << (double) (ends - start) / CLOCKS_PER_SEC << endl;
48 
49 
50 }

从这来看似乎二维能快一些，但是如果是两个一维和一个二维的话，还是一维要快的