PHP에서 연속 하위 배열의 최대 합을 찾는 문제에 대한 두 가지 솔루션

이 글에서는 PHP의 배열 순회, 판단, 계산 및 기타 관련 운영 기술을 포함하여 PHP에서 연속 하위 배열의 최대 합을 찾는 문제에 대한 두 가지 솔루션을 주로 소개합니다. 도움이 필요한 친구들은 이를 참조할 수 있습니다

이 글에서는 PHP 구현에 대해 설명합니다. 예제와 함께 연속 하위 배열의 최대 합을 찾는 문제에 대한 두 가지 솔루션입니다. 참조용으로 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

문제 설명

부분 배열의 최대 합 찾기

문제 설명:

정수 배열을 입력하세요. 배열의 음수.
배열에 있는 하나 이상의 연속된 정수는 하위 배열을 형성하며, 각 하위 배열에는 합계가 있습니다.
모든 하위 배열의 합계의 최대값을 찾습니다. 필요한 시간 복잡도는 O(n)입니다.

연속 하위 배열의 최대 합에 대해 두 가지 해결책이 있습니다. 하나는 동적 프로그래밍입니다.

해결 방법은 다음과 같습니다.

function getMaxSubSum($arr){
  $curSum = $arr[0];
  $maxSum = $arr[0];
  for($i = 1; $i < count($arr); $i++){
    if($curSum > 0) $curSum += $arr[$i];
    else $curSum = $arr[$i];
    if($curSum > $maxSum) $maxSum = $curSum;
  }
  return $maxSum;
}

다른 하나는 스캐닝 방법

function getMaxSubSum($arr){
  $curSum = 0;
  $maxSum = 0;
  for($i = 0; $i < count($arr); $i++ ){
    $curSum += $arr[$i];
    if($curSum <= 0) $curSum = 0;
    if($curSum > $maxSum) $maxSum = $curSum;
  }
  if($maxSum == 0){
    $maxSum = $arr[0];
    for($i = 1; $i < count($arr); $i++){
      if($maxSum < $arr[$i] ) $maxSum = $arr[$i];
    }
  }
  return $maxSum;
}

당신이 관심을 가질 만한 기사:

Ajax를 얻기 위한 PHP의 헤더 방법 및 콘텐츠에 대한 설명

위 내용은 PHP에서 연속 하위 배열의 최대 합을 찾는 문제에 대한 두 가지 솔루션의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!