最大子序列有关问题（c++实现）

最大子序列问题（c++实现）

描述：对于给出的K个整数的序列{ N₁, N₂, ..., N_K }.，其连续的子序列定义为 { N_i, N_i+1, ..., N_j }，其中1 <= i <= j <= K. 最大子序列是其连续子序列中元素之和最大的子序列。例如：对于 { -2, 11, -4, 13, -5, -2 }, 最大子序列为 { 11, -4, 13 }，最大和为20。编程找出其最大子序列。

输入：每个输入包含两行，第一行表示序列个数K，第二行为序列的K个元素，各元素间用空格分隔。

输出：最大子序列，如果存在具有相等最大和，则全部输出，每个序列一行。

input：

-10 1 2 3 4 -5 -23 3 7 -21

output：

1 2 3 4
3 7
分析：最大的子序列只可能从一个正数开始，我的思路是找出所有可能的子序列存在二维数组（要记录最大值及开始和结束的位置）中。
ps：未考虑存在“0”的情况。其实考虑0只是多出几组本质上一样的子序列。

 1 #include<iostream>
 2 using namespace std;
 3 
 4 //返回该整数列结束的位置（从这个正数到下个负数之前的位置）
 5 int cal(int a[],int n, int i)
 6 {
 7     for (int j = i; j < n; j++)
 8     {
 9         if (a[j + 1] < 0)
10             return j;
11     }
12 }
13 void sort(int a[][3],int n)
14 {
15     for (int i = 0; i < n-1; i++)
16     {
17         int max = 0;
18         for (int j = i; j < n; j++)
19         {
20             if (a[j][0] > a[max][0])
21                 max = j;
22         }
23         int x = a[max][0], y = a[max][1], z = a[max][2];
24         a[max][0] = a[i][0]; a[max][1] = a[i][1]; a[max][2] = a[i][2];
25         a[i][0] = x; a[i][1] = y; a[i][2] = z;
26     }
27 }
28 
29 int main()
30 {
31     static int N[100],n;
32     cin >> n;
33     for (int i = 0; i < n; i++)
34         cin >> N[i];
35     static int count, max[100][3];
36     int a;
37     for (int i = 0; i < n;i++)
38     {
39         if (N[i]>0)//每一个正数段都找出一个可能的最大子序列
40         {
41             max[count][1] = i;
42             int sum = 0;
43             for (int j = i; j < n; j++)
44             {
45                 sum += N[j];
46                 if (sum>max[count][0])
47                 {
48                     max[count][0] = sum;
49                     max[count][2] = j;
50                 }
51             }
52             count++;
53             i += cal(N, n, i);
54         }    
55     }
56     //对可能最子序列按降序排序（由于可能存在多个最大子序列）
57     sort(max, count);
58     //输出最大的子序列
59     for (int i = 0; i < count; i++)
60     {
61         if (max[i][0] == max[0][0])
62         {
63             for (int j = max[i][1]; j < max[i][2]; j++)
64                 cout << N[j] << " ";
65             cout << N[max[i][2]] << endl;
66         }
67     }
68     system("pause");
69     return 0;
70 }

最大子序列有关问题（c++实现）

相关推荐