최대 하위 세그먼트 와 (3)
해법 3:
알고리즘 분석:
서열 a 에 대해 j 는 현재 서열 의 종점 을 대표 하고 i 는 현재 서열 의 출발점 을 대표 한다.
분석: a [i] 가 마이너스 라면 최대 서브 세그먼트 의 출발점 일 수 없습니다. a [i] 를 포함 하 는 모든 서브 세그먼트 가 통과 할 수 있 기 때 문 입 니 다. a [i + 1] 을 기점 으로 개선 되 었 습 니 다.유사 한 것 은 어떤 마이너스 부분 도 가장 좋 은 부분 접두사 가 될 수 없다 (원리 가 같다). 순환 에서 a [i] 에서 a [j] 까지 의 부분 이 마이너스 라면 i 를 추진 할 수 있 습 니 다.
결론: i + 1 까지 추진 할 수 있 을 뿐만 아니 라 j + 1 까지 계속 추진 할 수 있 습 니 다. 원인: p 를 i + 1 과 j 사이 의 임 의 표시 로 합 니 다.아래 표 시 된 p 의 임의의 부분 은 아래 표 시 된 i 보다 크 지 않 고 a [i] 에서 a [p - 1] 까지 의 부분 을 포함 합 니 다.
a [i] 부터 a [p - 1] 까지 이 부분 은 마이너스 가 아니 기 때 문 입 니 다.
알고리즘 구현:
public class MaxSum
{
public static int maxSubSum(int[] a)
{
int maxSum = 0;
int thisSum = 0;
for (int j = 0; j < a.length; j++)
{
thisSum += a[j];
if (thisSum > maxSum)
{
maxSum = thisSum;
}
else if (thisSum < 0)
{
thisSum = 0;
}
}
return maxSum;
}
public static void main(String[] args)
{
int[] a = {-2, 11, -4, 13, -5, -2};
System.out.println(MaxSum.maxSubSum(ar));
}
}알고리즘 의 장점:
1) 운행 시간 이 가장 짧다.
2) 데 이 터 를 한 번 만 스 캔 하고 a [i] 가 읽 히 고 처리 되면 기억 할 필요 가 없습니다.
3) 알고리즘 은 언제든지 읽 은 데이터 에 대해 이 문제 의 정 답 을 제시 할 수 있다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
