给定一个由1和0组成的字符串。任务是找到字符串段的最大长度，使每个段中的1大于0。 注： 每个片段都应该是不同的。索引从0开始。 例如：
null
输入： str=“100110001010001” 输出： 9 从索引0到4（10011）的第一段，总长度=5 从索引8到索引10（101）的第二段，总长度=3 从索引14到14（1）的第三段，总长度=1， 因此答案是5+3+1=9 输入： str=“00101111000” 输出： 13 最大长度可通过分段形成 从索引0到索引12（00101111000）， i、 e.总长度=13
方法：
- 如果start==n，则出现限制条件，返回0。
- 从开始到n运行一个循环，计算每个子阵列直到n。
- 如果字符为1，则递增计数1，否则递增计数0。
- 如果计数1大于0，则递归调用索引（k+1）的函数，即下一个索引，并添加剩余长度，即k-start+1。
- 否则只递归调用下一个索引k+1的函数。
- 返回dp[开始]。
以下是上述方法的实施情况：
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Recursive Function to find total length of the array // Where 1 is greater than zero int find( int start, string adj, int n, int dp[]) { // If reaches till end if (start == n) return 0; // If dp is saved if (dp[start] != -1) return dp[start]; dp[start] = 0; int one = 0, zero = 0, k; // Finding for each length for (k = start; k < n; k++) { // If the character scanned is 1 if (adj[k] == '1' ) one++; else zero++; // If one is greater than zero, add total // length scanned till now if (one > zero) dp[start] = max(dp[start], find(k + 1, adj, n, dp) + k - start + 1); // Continue with next length else dp[start] = max(dp[start], find(k + 1, adj, n, dp)); } // Return the value for start index return dp[start]; } // Driver Code int main() { string adj = "100110001010001" ; // Size of string int n = adj.size(); int dp[n + 1]; memset (dp, -1, sizeof (dp)); // Calling the function to find the value of function cout << find(0, adj, n, dp) << endl; return 0; } |
JAVA
// Java implementation of // above approach import java.util.*; import java.lang.Math; class GFG { // Recursive Function to find // total length of the array // Where 1 is greater than zero public static int find( int start, String adj, int n, int dp[]) { // If reaches till end if (start == n) return 0 ; // If dp is saved if (dp[start] != - 1 ) return dp[start]; dp[start] = 0 ; int one = 0 , zero = 0 , k; // Finding for each length for (k = start; k < n; k++) { // If the character scanned is 1 if (adj.charAt(k) == '1' ) one++; else zero++; // If one is greater than // zero, add total length // scanned till now if (one > zero) dp[start] = Math.max(dp[start], find(k + 1 , adj, n, dp) + k - start + 1 ); // Continue with next length else dp[start] = Math.max(dp[start], find(k + 1 , adj, n, dp)); } return dp[start]; } // Driver code public static void main (String[] args) { String adj = "100110001010001" ; // Size of string int n = adj.length(); int dp[] = new int [n + 1 ]; Arrays.fill(dp, - 1 ); // Calling the function to find // the value of function System.out.println(find( 0 , adj, n, dp)); } } // This code is contributed // by Kirti_Mangal |
Python3
# Python 3 implementation of above approach # Recursive Function to find total length # of the array where 1 is greater than zero def find(start, adj, n, dp): # If reaches till end if (start = = n): return 0 # If dp is saved if (dp[start] ! = - 1 ): return dp[start] dp[start] = 0 one = 0 zero = 0 # Finding for each length for k in range (start, n, 1 ): # If the character scanned is 1 if (adj[k] = = '1' ): one + = 1 else : zero + = 1 # If one is greater than zero, add # total length scanned till now if (one > zero): dp[start] = max (dp[start], find(k + 1 , adj, n, dp) + k - start + 1 ) # Continue with next length else : dp[start] = max (dp[start], find(k + 1 , adj, n, dp)) # Return the value for start index return dp[start] # Driver Code if __name__ = = '__main__' : adj = "100110001010001" # Size of string n = len (adj) dp = [ - 1 for i in range (n + 1 )] # Calling the function to find the # value of function print (find( 0 , adj, n, dp)) # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of above approach using System; class GFG { // Recursive Function to find total length of the array // Where 1 is greater than zero public static int find( int start, string adj, int n, int [] dp) { // If reaches till end if (start == n) return 0; // If dp is saved if (dp[start] != -1) return dp[start]; dp[start] = 0; int one = 0, zero = 0, k; // Finding for each length for (k = start; k < n; k++) { // If the character scanned is 1 if (adj[k] == '1' ) one++; else zero++; // If one is greater than zero, add total // length scanned till now if (one > zero) dp[start] = Math.Max(dp[start], find(k + 1, adj, n, dp) + k - start + 1); // Continue with next length else dp[start] = Math.Max(dp[start], find(k + 1, adj, n, dp)); } // Return the value for start index return dp[start]; } // Driver Code static void Main() { string adj = "100110001010001" ; // Size of string int n = adj.Length; int [] dp = new int [n + 1]; for ( int i = 0; i <= n; i++) dp[i] = -1; // Calling the function to find the value of function Console.Write(find(0, adj, n, dp) + "" ); } //This code is contributed by DrRoot_ } |
PHP
<?php // PHP implementation of above approach // Recursive Function to find total length // of the array where 1 is greater than zero function find( $start , $adj , $n , $dp ) { // If reaches till end if ( $start == $n ) return 0; // If $dp is saved if ( $dp [ $start ] != -1) return $dp [ $start ]; $dp [ $start ] = 0; $one = 0; $zero = 0; // Finding for each length for ( $k = $start ; $k < $n ; $k ++) { // If the character scanned is 1 if ( $adj [ $k ] == '1' ) $one ++; else $zero ++; // If one is greater than zero, add total // length scanned till now if ( $one > $zero ) $dp [ $start ] = max( $dp [ $start ], find( $k + 1, $adj , $n , $dp ) + $k - $start + 1); // Continue with next length else $dp [ $start ] = max( $dp [ $start ], find( $k + 1, $adj , $n , $dp )); } // Return the value for $start index return $dp [ $start ]; } // Driver Code $adj = "100110001010001" ; // Size of string $n = strlen ( $adj ); $dp = array_fill (0, $n + 1, -1); // Calling the function // to find the value of function echo find(0, $adj , $n , $dp ); // This code is contributed by ihritik ?> |
Javascript
<script> // javascript implementation of // above approach // Recursive Function to find // total length of the array // Where 1 is greater than zero function find(start, adj , n , dp) { // If reaches till end if (start == n) return 0; // If dp is saved if (dp[start] != -1) return dp[start]; dp[start] = 0; var one = 0, zero = 0, k; // Finding for each length for (k = start; k < n; k++) { // If the character scanned is 1 if (adj[k] == '1' ) one++; else zero++; // If one is greater than // zero, add total length // scanned till now if (one > zero) dp[start] = Math.max(dp[start], find(k + 1, adj, n, dp) + k - start + 1); // Continue with next length else dp[start] = Math.max(dp[start], find(k + 1, adj, n, dp)); } return dp[start]; } // Driver code var adj = "100110001010001" ; // Size of string var n = adj.length; var dp = Array(n + 1).fill(-1); // Calling the function to find // the value of function document.write(find(0, adj, n, dp)); // This code is contributed by umadevi9616 </script> |
输出：
9
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
