我有这个问题,但我不确定解:给定一个整数数组A,计算它最长的奇偶增长子序列(LOEIS)的长度,即A中元素的最长序列S的长度,使得S的所有元素都是奇数或偶数。例如,给定: A=3,9,4,8,6,13,10,26,16,18,因为最长的偶数序列由5个元素组成: 4,6,10,16,18我们有LOEIS(A)=5。
如何编写这样的函数?谢谢!
发布于 2022-05-09 07:17:34
这里有一个来自https://www.geeksforgeeks.org/python-program-for-longest-increasing-subsequence/的解决方案,我已经适应了您的要求:
import matplotlib.pyplot as plt
import numpy as np
# A naive Python implementation of LIS problem
""" To make use of recursive calls, this function must return
two things:
1) Length of LIS ending with element arr[n-1]. We use
max_ending_here for this purpose
2) Overall maximum as the LIS may end with an element
before arr[n-1] max_ref is used this purpose.
The value of LIS of full array of size n is stored
in * max_ref which is our final result """
# global variable to store the maximum
global maximum
def _lis(arr, n):
# to allow the access of global variable
global maximum
# Base Case
if n == 1:
return 1
# maxEndingHere is the length of LIS ending with arr[n-1]
maxEndingHere = 1
"""Recursively get all LIS ending with arr[0], arr[1]..arr[n-2]
IF arr[n-1] is smaller than arr[n-1], and max ending with
arr[n-1] needs to be updated, then update it"""
for i in range(1, n):
res = _lis(arr, i)
if arr[i - 1] < arr[n - 1] and res + 1 > maxEndingHere:
maxEndingHere = res + 1
# Compare maxEndingHere with overall maximum. And
# update the overall maximum if needed
maximum = max(maximum, maxEndingHere)
return maxEndingHere
def lis(arr):
# to allow the access of global variable
global maximum
# length of arr
n = len(arr)
# maximum variable holds the result
maximum = 1
# The function _lis() stores its result in maximum
_lis(arr, n)
return maximum
A=np.array([3,9,4,8,6,13,10,26,16,18])
Even = A[A%2==0]
Odd = A[A%2==1]
print(Even,Odd)
print("Length of lis for Even is", lis(Even))
print("Length of lis for Odd is", lis(Odd))偶数的
长为5,奇数为3
。
https://stackoverflow.com/questions/72168092
复制相似问题