1之后没有0的最长子序列

给定一个二进制数组,求最长子序列的长度,使1后面没有0。

null

例如:

Input : 1 1 0 1Output : 3Explanation : If we remove 0 from the array, then nozero comes right after one (satisfying the condition) and the maximum game left are 3 (i.e. 1 1 1)Input : 0Output : 1Explanation : Since he wants to save maximum game inthe array. He doesn't remove any game. 

让我们找出这个序列中有多少个零,然后取最后一个零之后的所有零。在每一步中,从序列的开始处取下一个零,然后数一数后面的数字。用最大值更新答案。 你可以预先计算后缀上的数字。 例如。 0 1 0 0 1 1 1 计算后缀后,数组将变为: 0 4 0 0 3 2 1 从开始移动到结束,每次在数组中找到零时,numberofzeros递增1。如果数组[index]不是零,则res=max(res,numberofzeros+该索引处数组的值)。 循环之后:res=max(res,numberofzeros)

C++

// CPP program to find longest subsequence
// such that there is no 0 after 1.
#include <bits/stdc++.h>
using namespace std;
int maxSubseq( int vec[], int n) {
// Store the count of number of ones
// from right to left in the array
int suffix = 0;
for ( int i = n - 1; i >= 0; i--)
{
if (vec[i] == 1)
{
suffix++;
vec[i] = suffix;
}
}
// Traverse from left to right, keep count
// of 0s and for every 0, check number of
// 1s after it. Update the result if needed.
int res = 0;
int zero = 0;
for ( int i = 0; i < n; i++)
{
if (vec[i] == 0)
zero++;
// Checking the maximum size
if (vec[i] > 0)
res = max(res, zero + vec[i]);
}
// Checking the maximum size
return max(res, zero);
}
// Driver Code
int main()
{
int input[] = { 0, 1, 0, 0, 1, 0 };
int n = sizeof (input) / sizeof (input[0]);
cout << maxSubseq(input, n);
return 0;
}


JAVA

// java program to find longest subsequence
// such that there is no 0 after 1.
import java.io.*;
public class GFG {
static int maxSubseq( int []vec, int n)
{
// Store the count of number of
// ones from right to left in
// the array
int suffix = 0 ;
for ( int i = n - 1 ; i >= 0 ; i--)
{
if (vec[i] == 1 )
{
suffix++;
vec[i] = suffix;
}
}
// Traverse from left to right, keep
// count of 0s and for every 0, check
// number of 1s after it. Update the
// result if needed.
int res = 0 ;
int zero = 0 ;
for ( int i = 0 ; i < n; i++)
{
if (vec[i] == 0 )
zero++;
// Checking the maximum size
if (vec[i] > 0 )
res = Math.max(res, zero + vec[i]);
}
// Checking the maximum size
return Math.max(res, zero);
}
// Driver Code
static public void main (String[] args)
{
int []input = { 0 , 1 , 0 , 0 , 1 , 0 };
int n = input.length;
System.out.println(maxSubseq(input, n));
}
}
// This code is contributed by vt_m.


Python3

# Python 3 program to find longest subsequence
# such that there is no 0 after 1.
def maxSubseq(vec, n):
# Store the count of number of ones
# from right to left in the array
suffix = 0
i = n - 1
while (i > = 0 ):
if (vec[i] = = 1 ):
suffix + = 1
vec[i] = suffix
i - = 1
# Traverse from left to right, keep count
# of 0s and for every 0, check number of
# 1s after it. Update the result if needed.
res = 0
zero = 0
for i in range ( 0 ,n, 1 ):
if (vec[i] = = 0 ):
zero + = 1
# Checking the maximum size
if (vec[i] > 0 ):
res = max (res, zero + vec[i])
# Checking the maximum size
return max (res, zero)
# Driver code
if __name__ = = '__main__' :
input = [ 0 , 1 , 0 , 0 , 1 , 0 ]
n = len ( input )
print (maxSubseq( input , n))
# This code is contributed by
# Surendra_Gangwar


C#

// C# program to find longest subsequence
// such that there is no 0 after 1.
using System;
public class GFG {
static int maxSubseq( int []vec, int n)
{
// Store the count of number of
// ones from right to left in
// the array
int suffix = 0;
for ( int i = n - 1; i >= 0; i--)
{
if (vec[i] == 1)
{
suffix++;
vec[i] = suffix;
}
}
// Traverse from left to right, keep
// count of 0s and for every 0, check
// number of 1s after it. Update the
// result if needed.
int res = 0;
int zero = 0;
for ( int i = 0; i < n; i++)
{
if (vec[i] == 0)
zero++;
// Checking the maximum size
if (vec[i] > 0)
res = Math.Max(res, zero + vec[i]);
}
// Checking the maximum size
return Math.Max(res, zero);
}
// Driver Code
static public void Main ()
{
int []input = { 0, 1, 0, 0, 1, 0 };
int n = input.Length;
Console.WriteLine(maxSubseq(input, n));
}
}
// This code is contributed by vt_m.


PHP

<?php
// PHP program to find longest
// subsequence such that there
// is no 0 after 1.
function maxSubseq( $vec , $n )
{
// Store the count of
// number of ones from
// right to left in
// the array
$suffix = 0;
for ( $i = $n - 1;
$i >= 0; $i --)
{
if ( $vec [ $i ] == 1)
{
$suffix ++;
$vec [ $i ] = $suffix ;
}
}
// Traverse from left to
// right, keep count of
// 0s and for every 0,
// check number of 1s after
// it. Update the result if
// needed.
$res = 0;
$zero = 0;
for ( $i = 0; $i < $n ; $i ++)
{
if ( $vec [ $i ] == 0)
$zero ++;
// Checking the
// maximum size
if ( $vec [ $i ] > 0)
$res = max( $res , $zero +
$vec [ $i ]);
}
// Checking the
// maximum size
return max( $res , $zero );
}
// Driver Code
$input = array (0, 1, 0, 0, 1, 0);
$n = count ( $input );
echo maxSubseq( $input , $n );
// This code is contributed
// by anuj_67.
?>


Javascript

<script>
// Javascript program to find longest subsequence
// such that there is no 0 after 1.
function maxSubseq(vec, n)
{
// Store the count of number of
// ones from right to left in
// the array
let suffix = 0;
for (let i = n - 1; i >= 0; i--)
{
if (vec[i] == 1)
{
suffix++;
vec[i] = suffix;
}
}
// Traverse from left to right, keep
// count of 0s and for every 0, check
// number of 1s after it. Update the
// result if needed.
let res = 0;
let zero = 0;
for (let i = 0; i < n; i++)
{
if (vec[i] == 0)
zero++;
// Checking the maximum size
if (vec[i] > 0)
res = Math.max(res, zero + vec[i]);
}
// Checking the maximum size
return Math.max(res, zero);
}
let input = [ 0, 1, 0, 0, 1, 0 ];
let n = input.length;
document.write(maxSubseq(input, n));
</script>


输出:

4

本文由 萨钦·比什特 .如果你喜欢GeekSforgek,并想贡献自己的力量,你也可以使用 写极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上,并帮助其他极客。 如果您发现任何不正确的地方,或者您想分享有关上述主题的更多信息,请写下评论。

© 版权声明
THE END
喜欢就支持一下吧,技术咨询可以联系QQ407933975
点赞7 分享