문자열 분할 후 최대 점수

<?php
/**
 * @param String $s
 * @return Integer
 */
function maxScore($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$s1 = "011101";
$s2 = "00111";
$s3 = "1111";

echo "Input: $s1, Output: " . maxScore($s1) . PHP_EOL; // Output: 5
echo "Input: $s2, Output: " . maxScore($s2) . PHP_EOL; // Output: 5
echo "Input: $s3, Output: " . maxScore($s3) . PHP_EOL; // Output: 3
?>




<h3>
  
  
  설명:
</h3>

<ol>
<li><p><strong>접두사 합계 계산</strong>: $prefixOneCount 배열에서 1의 접두사 합계를 계산합니다. 여기서 각 인덱스는 해당 지점까지의 1의 누적 개수를 보유합니다.</p></li>
<li>
<p><strong>가능한 분할 반복</strong>: 각 인덱스 i(0에서 n-2)를 통해 반복을 시작합니다. 여기서 문자열은 왼쪽 부분(0에서 i)과 오른쪽 부분( i 1부터 n-1까지).</p>

<ul>
<li>각 분할에 대해 왼쪽 하위 문자열($zeroCountLeft)에서 0의 개수를 셉니다.</li>
<li>미리 계산된 $prefixOneCount를 사용하여 올바른 하위 문자열에 몇 개가 있는지 계산하세요.</li>
</ul>
</li>
<li><p><strong>점수 계산</strong>: 각 분할의 점수는 왼쪽 부분의 0과 오른쪽 부분의 1의 합으로 계산됩니다. 이번 반복 중에 발생하는 최대 점수를 업데이트합니다.</p></li>
<li><p><strong>최종 결과</strong>: 이 함수는 모든 분할 중에 발견된 최대 점수를 반환합니다.</p></li>
</ol>

<h3>
  
  
  복잡성:
</h3>

<ul>
<li>
<p><strong>시간 복잡도</strong>: <em><strong>O(n)</strong></em></p>

<ul>
<li>접두사 합계를 미리 계산하고 문자열을 반복하는 데는 모두 <em><strong>O(n)</strong></em>.</li>이 소요됩니다.
<li>점수를 계산하기 위해 문자열을 반복하는 데에도 O(n)이 필요합니다.</li>
<li>따라서 총 시간 복잡도는 O(n)이며, 이는 주어진 입력 크기(n ≤ 500)에 효율적입니다.</li>
</ul>


</li>

<li>

<p><strong>공간 복잡도</strong>: <em><strong>O(n)</strong></em></p>

<ul>
<li>접두사 합계 배열에는 <em><strong>O(n)</strong></em> 추가 공간이 필요합니다.</li>
</ul>


</li>

</ul>

<h3>
  
  
  예:
</h3>



<pre class="brush:php;toolbar:false">echo maxScore("011101"); // Output: 5
echo maxScore("00111");  // Output: 5
echo maxScore("1111");   // Output: 3