首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何在python中找到最长的奇偶增长子序列?

问如何在python中找到最长的奇偶增长子序列?
EN

Stack Overflow用户
提问于 2022-05-09 07:04:32
回答 1查看 68关注 0票数 -2

我有这个问题,但我不确定解:给定一个整数数组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。

如何编写这样的函数?谢谢!

EN

回答 1

Stack Overflow用户

发布于 2022-05-09 07:17:34

这里有一个来自https://www.geeksforgeeks.org/python-program-for-longest-increasing-subsequence/的解决方案,我已经适应了您的要求:

代码语言:javascript
复制
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

。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/72168092

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档