import java.util.Scanner;
class Motu
 {
    // Returns length of the longest subsequence
    // of the form 0*1*0*
    public static int longestSubseq(String s)
    {
        int n = s.length();
 

       
        int[] count_1 = new int[n   1];
        count_1[0] = 0;
        for (int j = 1; j <= n; j  )
         {
            count_1[j] = count_1[j - 1];
            if (s.charAt(j - 1) != '0')
                 count_1[j]  ;
         }
          
        // Compute result using precomputed values
        int ans = 0;
        for (int i = 1; i <= n; i  )
            for (int j = i; j <= n; j  )
                ans = Math.max(count_1[j] - count_1[i - 1] , ans);
                               
        return ans;
     }
 
    // Driver code
    public static void main(String[] args)
    {
        @SuppressWarnings("resource")
        Scanner sc=new Scanner(System.in);
        String s =sc.next();
        System.out.println(longestSubseq(s));
    }
}

I am trying to make a program to get maximum sequences 1 in a string containing 0's & 1's. But I am unable to make out the logic for it, my program prints a number of 1's in the string which is not my desired output.

Sample input:- 0011100111100
output:- 4

CodePudding user response：

You're quite good, but you're missing one thing : if the char is '0' : reset the counter to zero

for (int j = 1; j <= n; j  ) {
    if (s.charAt(j - 1) != '0')
        count_1[j] = count_1[j - 1]   1;
    else
        count_1[j] = 0;
}

But that can be done in one loop only, count with an int, and keep track of the max

public static int longestSubseq(String s) {
    int ans = 0;
    int count = 0;
    for (char c : s.toCharArray()) {
        if (c == '1')
            count  ;
        else
            count = 0;

        ans = Math.max(ans, count);
    }
    return ans;
}

CodePudding user response：

public static int longestSubSequence(String str, char ch) {
    int res = 0;
    int count = 0;

    for (int i = 0; i < str.length(); i  ) {
        count = str.charAt(i) == ch ? count   1 : 0;
        res = Math.max(res, count);
    }

    return res;
}

CodePudding user response：

As an alternative to the other answers that work with a for-loop:

You could split the sequence into groups of ones with regex. Next, just iterate over the groups and update the count, if the length of the group is bigger than the previous length.

The first group will be 111 and the next one 1111. Thus the count will first be 3 and then it will be updated to 4.

import java.util.regex.Pattern;
import java.util.regex.Matcher;

public class CountSubsequence {
     public static void main(String []args){
        String sequence = "0011100111100";
        Pattern pattern = Pattern.compile("(1 )");
        Matcher matcher = pattern.matcher(sequence);
        int count = 0;
        while (matcher.find()) {
            int currentLength = matcher.group().length();
            if (currentLength > count) count = currentLength;
        }
        System.out.println(count); // 4
     }
}

Since regex is not that performant you might want to use the for-loop in case you care for performance - but that just matters if you run it execute it a lot.

CodePudding user response：

The input string may be split by the characters that are not 1 (thus all non-1 characters are ignored and subsequences containing only 1 remain), and then the max length of the remaining parts can be found using Stream API:

public static int longestSubSequence(String str, char ch) {
    return Arrays.stream(str.split("[^"   ch   "]"))
                 .mapToInt(String::length)
                 .max()
                 .orElse(0);
}

Similarly, a matching pattern can be created, and the max length of the group can be found:

public static int longestSubSequence(String str, char ch) {
    return Pattern.compile(ch   " ")
            .matcher(str)
            .results()
            .map(MatchResult::group)
            .mapToInt(String::length)
            .max()
            .orElse(0);
}

Test:

System.out.println(longestSubSequence("00111011001111", '1')); // 4

It's worth mentioning that the characters other than '0' and '1' may be present in the input string, only subsequences of the given char are counted.