给定一个二进制数组,求最长子序列的长度,使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