Java教程

HNU暑假程序设计训练 0419

本文主要是介绍HNU暑假程序设计训练 0419,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

题目描述

思路分析

AC代码

深入思考


题目描述

给出一个由n个正整数组成的数组。您的任务是找到给定数组的递增子数组的最大长度。

递增子数组由数组中若干个连续元素组成,且子数组中的每个元素严格地大于前一个元素。

【输入形式】

第一行为一个正整数n(1≤n≤10^{5}),表示数组元素的个数

第二行给出n个正整数a1 a2......an  (1≤ai≤10^{9}) ,整数之间使用空格分隔
【输出形式】

输出最大递增子数组的长度
【样例输入】

5
1 7 2 11 15

【样例输出】

3

【样例说明】

1 7可以构成一个递增子数组

2 11 15可以构成一个递增子数组

所以本样例的输出结果为3

思路分析

直接采用穷举法,二重循环遍历,时间复杂度为O(n^{2})。

设一个数组int arr:

01234
172115

设整型变量cnt=1(任意长度大于0数组的最长连续递增子序列最小长度为1),记录当前子数组最长连续递增子序列的长度。子数组分割方法如下:

第一次arr[0],arr[1],arr[2],arr[3],arr[4]cnt=2
第二次arr[1],arr[2],arr[3],arr[4]cnt=1
第三次arr[2],arr[3],arr[4]cnt=3
第四次arr[3],arr[4]cnt=1
第五次arr[4]cnt=1

最终结果输出3。

AC代码

#include <iostream>
#include<stdio.h>
using namespace std;
int arr[100000]={0};
int main()
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    int Max=0;
    for(int i=0;i<n;i++)
    {
        int cnt=1;
        for(int j=i;j<n-1;j++)
        {
            if(arr[j]<arr[j+1])
            {
                cnt++;
            }
            else
            {
                break;
            }
        }
        if(cnt>Max)//取所有cnt中的最大值
        {
            Max=cnt;
        }
    }
    printf("%d\n",Max);
}

深入思考

其实这题是一个典型的动态规划问题的变式。

动态规划基本知识:

 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。

动态规划算法跟数组有着密切的关系,因此推荐大家在分析动态规划的算法时画一张表格(建议使用excel)分析解决问题往往能够事半功倍。
(引自 CSDN博主「静笃归心方得平和心气]
原文链接:https://blog.csdn.net/weixin_42182348/article/details/90814032)

最大递增子数组问题(不要求连续)

给定数组arr,返回arr的最长递增子序列(Longest increasing subsequence,LIS)的长度,比如arr=[2,1,5,3,6,4,8,9,7],最长递增子序列为[1,3,4,8,9]返回其长度为5。

那么,这个问题怎么用动态规划法求解呢?

设f[i]表示必须以arr[i]结尾的所有子数组的LIS。要计算f[i],就要考察i之前的所有位置(0到i-1,这就是代码内层for的控制变量j的变化范围),找到最大的f[j]。f[j]代表以arr[j]结尾的子数组中最大递增子序列的长度。

注意到,由于它是递增的,因此arr[j]就是子序列的最大值。如果arr[i]比arr[j]还大,那就一定大于该序列中的其他数,能够构成一个长度+1的LIS。这就是if中的第一个条件的来源。

第二个条件是为了保证更新f[i]的结果是得到更大的f[i]值。说起来不太直观,请看下表。

序号i01234...
arr[i]111319521...
f[i]1231...

此刻i=4。假设没有if中的第二个条件(f[i]<f[j]+1),求f[4]的详细过程为:

j0123
f[4]2342

arr[0]<arr[4]                             f[4]=f[0]+1=2

arr[1]<arr[4]                             f[4]=f[1]+1=3

arr[2]<arr[4]                             f[4]=f[2]+1=4

arr[3]<arr[4] 但是此时f[3]=1,f[4]=4(见上一行), 不满足f[i]<f[j]+1。更新后 f[4]=f[3]+1=2(反而变小了)

而带上(f[i]<f[j]+1)这个条件的话,j=3这次循环就不会更新f[4]的值,最终算出f[4]的正确值为4。

代码

#include <iostream>
#include<stdio.h>
using namespace std;
int arr[100000]={0};
int f[100000]={0};//记录子数组的LIS。
int main()
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> arr[i];
        f[i]=1;//初始化
    }
    int Max=0;//记录以不同元素结尾的子数组的LIS的最大值。
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
          if((arr[j]<arr[i])&& (f[i]<f[j]+1))
          {
              f[i]=f[j]+1;//f[i]记录了必须以arr[i]结尾时所有子数组的LIS。
          }
        }
        if(f[i]>Max)
        {
            Max=f[i];
        }
    }
    cout << Max << endl;
    return 0;
}

这篇关于HNU暑假程序设计训练 0419的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!