이진 문자열에서 증가하지 않는 가장 긴 하위 시퀀스

이 문제에서는 주어진 문자열에서 증가하지 않는 가장 긴 부분 수열을 찾아야 합니다.

비증가는 문자가 동일하거나 내림차순임을 의미합니다. 이진 문자열에는 "0"과 "1"만 포함되므로 결과 문자열은 "1"로 시작하고 "0"으로 끝나거나 "0" 또는 "1"로 시작하고 끝나야 합니다.

이 문제를 해결하기 위해 문자열의 각 위치에서 접두사 "1"과 접미사 "0"을 세고 접두사 "1"과 접미사 "0"의 최대 합을 구합니다.

문제 설명 - 바이너리 문자열 str이 제공됩니다. 주어진 문자열에서 증가하지 않는 가장 긴 부분 수열을 찾아야 합니다.

예

으아악 으아악

지침

가장 긴 비증가 부분 수열은 "1100"입니다.

으아악 으아악

지침

가장 긴 비증가 부분 수열은 "111000"입니다.

으아악 으아악

지침

가장 긴 비증가 하위 수열은 '00000000'이며, 이는 주어진 문자열과 같습니다.

방법 1

이 방법에서는 배열의 각 인덱스에 대해 접두사 '1'과 접미사 '0'의 개수를 저장합니다. 그런 다음 두 배열의 동일한 인덱스에서 값을 가져와 추가하고 최대 합계를 찾습니다.

알고리즘

• 1단계 - pre1s 및 suffix0s 배열을 정의하여 접두사 1과 접미사 0을 저장합니다. 또한 모든 배열 요소를 0으로 초기화합니다.

• 2단계 - for 루프를 사용하여 문자열을 반복하고 각 인덱스의 접두사 1을 계산합니다. i > 0이면 이전 요소의 값이 현재 요소에 추가됩니다.

• 3단계 - 현재 문자가 "1"이면 pre1s[i]의 현재 값에 1을 더합니다.

• 4단계 - 이제 주어진 문자열에서 접미사 0을 셉니다. 끝부터 시작하여 문자열을 탐색합니다.

• 5단계 - "I" 값이 "n – 1"과 같지 않으면 "I + 1" 요소의 값을 가져와 현재 요소에 추가합니다.

• 6단계 - 현재 요소가 "0"이면 현재 요소에 1을 추가합니다.

• 7단계 - 이제 "res" 변수를 0으로 초기화합니다.

• 8단계 - 루프를 사용하여 "pre1s" 및 "suffix0s"를 반복합니다.

• 9단계 - "pre1s" 및 "suffix0s" 배열의 i번째 인덱스에서 값을 가져와 함께 추가합니다. 또한 "sum"이 "res" 변수의 현재 값보다 큰 경우 "res" 변수 값이 "sum" 값으로 변경됩니다.

• 10단계 - "res" 변수의 값을 반환합니다.

예

입력 '010100'의 경우 접두사 배열은 [0, 1, 1, 2, 2, 2]이고 접미사 0 배열은 [4, 3, 3, 2, 2, 1]입니다. 합계 배열은 [4, 4, 4, 4, 4, 1]이고 합계 배열의 최대값은 4입니다. 그러므로 답은 4가 될 것이다.

으아악

출력

으아악

시간 복잡도 - O(N) 접두사 1과 접미사 0으로 배열을 초기화해야 하기 때문입니다.

공간 복잡도 - 배열에 접두사 1과 접미사 0을 저장하므로 O(N)

방법 2

이 방법에서는 먼저 총 0의 개수를 계산합니다. 그런 다음 문자열을 반복하면서 "1"을 계속 세고, 0이 발견되면 "0"씩 감소시킵니다. 또한 각 반복마다 0과 1의 개수를 더하고 최대 결과 값을 찾습니다.

알고리즘

• 1단계 - 'count1', 'count0' 및 'res' 변수를 정의하고 0으로 초기화하여 각각 1, 0의 개수와 최종 결과를 저장합니다.

• 2단계 - 문자열을 반복하고 "count0" 변수에 저장하여 총 0의 개수를 셉니다.

• 3단계 - 이제 루프를 사용하여 문자열을 반복합니다.

• 4단계 - 루프에서 현재 문자가 "1"이면 "count1"의 값을 1만큼 늘리고, 그렇지 않으면 "count0"의 값을 1만큼 줄입니다.

• 5단계 - 또한 "res" 및 "count0 + count1"의 최대값을 "res" 변수에 저장합니다.

• 6단계 - 루프가 종료되면 "res" 변수의 값을 반환합니다.

예

으아악

출력

으아악

시간 복잡도 - O(N) 문자열에 있는 0의 총 개수를 세고 문자열을 순회하여 가장 긴 부분 수열을 찾습니다.

공간 복잡성 - O(1)

결론

여기서 두 방법 모두 시간 복잡도는 동일하지만 공간 복잡도가 다릅니다. 두 번째 방법은 코드를 최적화할 때 일정한 공간을 사용하지만, 첫 번째 방법은 접두사 1과 접미사 0의 총 개수를 저장하기 위해 동적 공간을 사용합니다.

위 내용은 이진 문자열에서 증가하지 않는 가장 긴 하위 시퀀스의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!