第1关：最长上升子序列

任务描述

本关任务：求一个序列的最长上升子序列。

相关知识

最长上升子序列问题

当一个序列Bi满足B1 < B2 < ... < Bs的时候，我们称这个序列是上升的。对于给定的一个序列a1, a2, ..., aN，我们可以在其中找到一些上升的子序列。

现在给你一个序列，请你求出其中最长的上升子序列的长度。

比如一个序列1, 7, 3, 5, 9, 4, 8：

它的一些上升子序列包括1, 7, 9, 3, 4, 8等

而其中最长的上升子序列的长度是4，比如1, 3, 5, 8。

解题思路

我们可以将这个问题进行分解：

将“在全数列ak(k=1, 2, 3 … N)中求最长上升子序列”问题，分解成“求以ak(k=1, 2, 3 … N)为终点的最长上升子序列的长度"。其中终点的含义为一个上升子序列中最右边的那个数。

为此我们可以使用一个数组maxLen来存放这些信息，maxLen[k]代表以ak为终点的最长上升子序列的长度。

显然，maxLen[1]是等于1的，那么如何通过maxLen[n]求maxLen[n + 1]呢？

我们可以知道，对于一个数an+1，它一定能连接到在它之前，且比它小的元素的后面，如果以这个元素为终点的最长上升子序列的长度为k，则新的长度就为k + 1。

那么我们就得到：maxLen[n] = max{ maxLen[k], 其中k < n, 且a[k] < a[n]} + 1。

这样，我们就可以通过maxLen[1]，逐步的得到maxLen[n]了。

大致的程序结构为：

maxLen[1] = 1;

for 枚举从2到n，设当前为i

{

选出maxLen[1]到maxLen[i - 1]中最大，且对应的终点元素比ai要小的值max。

maxLen[i] = max + 1。

}
输出maxLen中最大的结果

至此程序结构已经大致完成，请你补全代码，完成本关任务。

编程要求

在右侧编辑器中有一个函数MaxUp，它有两个参数arr和len，代表一个数组和它的长度，其中len <= 100。

请在这个函数中补充代码，计算并输出arr中最大上升子序列的长度。

输入数据由评测系统读取，并传递给MaxUp函数。具体见测试说明。

测试说明

平台会对你编写的代码进行测试：

测试输入： 7 1 7 3 5 9 4 8

预期输出： 4

每组输入有两行，第一行有一个数n，第二行有n个数，是数组内容。

#include <iostream>
using namespace std;

void MaxUp(int arr[],int len)
{
    int maxlen[len],max_maxlen=-1;
	/**********   Begin   **********/
    maxlen[1]=1;
    for(int i=0; i<len; i++)
    {
        maxlen[i]=1;
        for(int j=0; j<i; j++)
        {
            if(arr[i]>arr[j])
            {
                maxlen[i]=max(maxlen[i],maxlen[j]+1);
                max_maxlen=max(max_maxlen,maxlen[i]);
            }
        }
    }
    cout<<max_maxlen;
	/**********   End   **********/
}

第2关：数字三角形

任务描述

本关任务：计算数字三角形的最佳路径和。

数字三角形的最佳路径和

有一个数字三角形，从三角形的顶部到底部有很多条不同的路径，路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。

对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。请找出最佳路径上的数字之和。

比如对于数字三角形：

1. 7
2. 3 8
3. 8 1 0
4. 2 7 4 4
5. 4 5 2 6 5

最佳的路径和是：7 + 3 + 8 + 7 + 5 = 30。

解题思路

对于这个题，我们也可以用递归方式解决，可以计算出所有的路径和，然后选出其中的最大值，比如：

1. int arr[10][10];
2. int height; //三角形的高度
3. int MaxSum(int n,int k)
4. {
5. if(n == height - 1)
6. {
7. //三角形的底层直接返回节点值
8. return arr[n][k];
9. }
10. //选择下一层的左边一个节点
11. int v1 = MaxSum(n + 1,k);
12. //选择下一层的右边一个节点
13. int v2 = MaxSum(n + 1,k + 1);
14. //选择两条路径中和最大的那一条
15. return max(v1,v2) + arr[n][k];
16. }

通过观察代码可以得出，计算MaxSum(n, k)和MaxSum(n, k + 1)时，都需要计算MaxSum(n + 1, k + 1)。这就造成了重复计算，影响了计算效率。

因此我们可以在第一次计算完成后记录下MaxSum(n + 1, k + 1)的结果，在之后的计算中直接使用。

可以设置一个数组maxSum，maxSum[n][k]代表以第n层第k个节点为根时，最佳路径的和。

由于上层数据依赖下层数据，因此我们采用从底向上的计算顺序。

显然对于三角形的底层，maxSum[height - 1][k]就等于对应的节点值，即arr[height - 1][k]。

接下来我们思考如何从n + 1层maxSum得到n层maxSum。

为了取到最大值，那么n层的每个节点的值应该选择与相邻的两个n + 1层节点的值中最大的一个求和，即maxSum[n][k] = max(maxSum[n + 1][k] , maxSum[n + 1][k + 1]) + arr[n][k]。

而且我们发现，每一层的maxSum只与下一层的maxSum有关，那么我们只需要一个一维数组来存储maxSum即可。

因此得到的大致程序结构如下：

1. 设置maxSum为三角形底层各节点的值
2. for 遍历层数
3. {
4. 遍历maxSum，选出相邻两个元素中最大的一个，加上数字三角形中对应位置的节点值。
5. 将求出的值写回到maxSum的适当位置
6. }

至此程序结构已经大致完成，请你补全代码，完成本关任务。

编程要求

右侧编辑器中有一个函数MaxSum，它有两个参数arr和wid，其中wid <= 10。

arr是一个二维数组，有wid层，第一层（即arr[0]）有1个元素，第二层（即arr[1]）有2个元素，以此类推。数字三角形每一层的值，是从索引0开始，连续的存放在每一层对应的数组中的。

请你在这个函数中补充代码，计算并输出这个数字三角形的最佳路径和，占一行。具体见测试说明。

测试说明

平台会对你编写的代码进行测试：

预期输入： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

预期输出： 30

每组输入分为多行，第一行是一个整数wid，下面wid行为三角形的内容。

#include <iostream>
#include <algorithm>
using namespace std;

void MaxSum(int arr[][10], int wid)
{
	/**********   Begin   **********/
	int maxsum [wid][wid];
	for(int i=0;i<wid;i++) maxsum[wid-1][i]=arr[wid-1][i];
	for(int i=wid-2;i>=0;i--)
	{
		for(int j=i;j>=0;j--) maxsum[i][j]=max(maxsum[i+1][j],maxsum[i+1][j+1])+arr[i][j];
	}
	cout<<maxsum[0][0];
	/**********   End   **********/
}