我要招人

去企业版

首页 > 试题广场 >

牛牛的数列

[编程题]牛牛的数列

热度指数：5437 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛现在有一个n个数组成的数列,牛牛现在想取一个连续的子序列,并且这个子序列还必须得满足:最多只改变一个数,就可以使得这个连续的子序列是一个严格上升的子序列,牛牛想知道这个连续子序列最长的长度是多少。

输入描述:

输入包括两行,第一行包括一个整数n(1 ≤ n ≤ 10^5),即数列的长度;
第二行n个整数a_i, 表示数列中的每个数(1 ≤ a_i ≤ 10^9),以空格分割。

输出描述:

输出一个整数,表示最长的长度。

示例1

输入

6 
7 2 3 1 5 6

输出

算法知识视频讲解

Python

牛客122632865号

while True:
try:
m = int(input())
str = input().split(' ')
maxLen = 0
tmp = 0
for i in range(2,len(str)-1):
leftLen = 0
rightLen = 0
if int(str[i+1]) > int(str[i-1]):
for j in range(i-1,0,-1):

if int(str[j]) - int(str[j-1])>0:
leftLen += 1
else:
break

for j in range(i+1,m-1,1):
if int(str[j]) - int(str[j+1])<0:
rightLen += 1
else:
break
if leftLen+rightLen+3>maxLen:
maxLen = leftLen+rightLen+3
print(maxLen)
except:
break

发表于 2021-09-09 11:45:29 回复(0)

Python

FrogJackey

思路很简单：就是对每个元素相邻三元素间都寻找波峰和波谷，找到后向左，向右寻找最长递增序列，用一个tuple记录起始索引和序列长度，如果找到的新序列长度比它长，替换，最后输出最长子序列长度。这道题是可以用动态规划做的，写递推式。

import sys
def fun(values):
    i = 1
    record=[]
    while (i <= len(values) - 2):
        if(values[i - 1] > values[i] and values[i] < values[i + 1]&nbs***bsp; ### through of wave
          (values[i-1] < values[i] and values[i] > values[i + 1])):   ### peak of wave
            if (values[i + 1] >= values[i - 1]): ######### right > left
                j = i - 1
                while(j>=1 and values[j-1]<=values[j]): # find left longest subsequence
                    j=j-1

                k=i+2
                while (k <= len(values) - 1 and values[k] >= values[k - 1]): # find right longest subsequence
                    k+= 1

                if(len(record)==0):record.append((j,k-j))  ####for the subsequence: subscript is j, superscript is k-1
                else:
                    s_index,s_len=record[0]
                    if(k-j>s_len): record[0]=(j,k-j)

        i+=1 ################# check each element, rather than check continuous 3 elements

    final_index,final_len=record[0]
    # print(final_index,values[final_index],final_len)
    print( final_len)

if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())
    line = sys.stdin.readline().strip()
    values = list(map(int, line.split()))
    fun(values)

编辑于 2020-03-05 18:48:58 回复(0)

Python

墨痕201910151748921

def deal_A(A):

left = [1 for i in range(len(A))]

right = [1 for i in range(len(A))]

ans = 1

for i in range(1, len(A)):

if A[i] - A[i-1] > 0:

left[i] = left[i- 1] + 1

for i in range(len(A) - 2, -1, -1):

if A[i] < A[i+1]:

right[i] = right[i+1] + 1

for i in range(1, len(A) - 1):

if A[i-1] < A[i+1]:

sum = left[i-1] + right[i+1]

if sum > ans:

ans = sum

return ans + 1

if __name__ == "__main__":

n = int(input())

A = list(map(int, input().strip().split()))

print(deal_A(A))

发表于 2020-02-28 12:37:42 回复(0)

Python

绝无*仅有

def findString():
    length = input("请输入长度:")
    string = input("请输入%s位数列(空格分开):"%length)
    strList = string.split(" ")
    resultList = []
    for i in  range(0,eval(length)):
        n = 0
        result = strList[i]
        for s in strList[i+1:]:
            if s>result[len(result)-1]:
                result+=s
            elif s <result[len(result)-1] and n<1:
                result+=str(eval(result[len(result)-1])+1)
                n+=1
            else:
                break
        resultList.append(result)
    resultLen=len(resultList[0])
    for i in range(0,len(resultList)):
        print(resultList[i])
        if len(resultList[i])>resultLen:
            resultLen = len(resultList[i])
    print(resultLen)
findString()

发表于 2017-11-09 19:50:51 回复(0)

Python

华仔17

import sys

def Main(strs):
	n = int(strs)
	li = map(int,sys.stdin.readline().strip().split())
	if n == 1:
		return 1
	num = []
	count = 1
	maxval = 0
	for i in xrange(1,n):
		if li[i]<=li[i-1]:
			num.append(count)
			count = 0
		count += 1
	if count !=0:
		num.append(count)
	if len(num) == 1:
		return num[0]
	sumval = 0
	for i in xrange(len(num)-1):
		sumval += num[i]
		if num[i+1] != 1:
			if (li[sumval-1]+1<li[sumval+1] or li[sumval-2]+1<li[sumval]) and num[i] + num[i+1] > maxval:
				maxval = num[i]+ num[i+1]
		else:
			if num[i] + 1 > maxval:
				maxval = num[i]+ num[i+1]
	return maxval
while True:
	strs = sys.stdin.readline().strip()
	if not strs:
		break
	print Main(strs)

发表于 2017-05-23 13:18:56 回复(1)