최대 하위 시퀀스 와 (O (n)

다음은 선형 알고리즘 을 소개 한다. 이 알고리즘 은 많은 똑똑 한 알고리즘 의 전형 이다. 운행 시간 은 뚜렷 하지만 정확성 은 뚜렷 하지 않다 (이해 하기 어렵다).
/ / 선형 알고리즘 O (N) 

long maxSubSum4(const vector<int>& a) 
{ 
       long maxSum = 0, thisSum = 0; 
       for (int j = 0; j < a.size(); j++) 
       { 
              thisSum += a[j]; 
              if (thisSum > maxSum) 
                     maxSum = thisSum; 
              else if (thisSum < 0) 
                     thisSum = 0; 
       } 
       return maxSum; 
} 

    시간 계 O (N) 가 정확 하 다 는 것 을 쉽게 이해 할 수 있 지만 왜 정확 한 지 알 아내 기 가 힘 들 어 요.사실 이것 은 알고리즘 2 의 개선 이다.분석 할 때 도 i 는 현재 서열 의 출발점 이 고 j 는 현재 서열 의 종점 을 대표 한다.만약 우리 가 가장 좋 은 하위 서열 의 위 치 를 알 필요 가 없다 면 i 는 최적화 할 수 있다.
    중요 한 사상 은 만약 에 a [i] 가 마이너스 라면 가장 서열 적 인 출발점 을 대표 할 수 없다 는 것 이다. 왜냐하면 a [i] 를 포함 하 는 출발점 으로 하 는 모든 하위 서열 은 a [i + 1] 을 기점 으로 개선 할 수 있 기 때문이다.유사 한 것 은 모든 마이너스 서열 이 가장 좋 은 하위 서열 의 접두사 가 될 수 없다 는 것 이다.예 를 들 어 순환 에서 우 리 는 a [i] 에서 a [j] 까지 의 하위 서열 이 마이너스 라 는 것 을 감지 하면 우 리 는 i 를 추진 할 수 있다.관건 적 인 결론 은 우리 가 i + 1 까지 추진 할 수 있 을 뿐만 아니 라 실제 적 으로 j + 1 까지 추진 할 수 있다 는 것 이다.
    
예 를 들 면
p
예.
i+1
도착 하 다
j
사이 의 어떤 하 표 도 앞에서 가설 하 였 기 때문이다.
a[i]+…+a[j]
마이너스 라면 아래 표 시 를 시작 합 니 다.
p
임의의 하위 서열 은 아래 표 보다 크 지 않 습 니 다.
i
그리고
a[i]
도착 하 다
a[p-1]
하위 시퀀스 에 대응 하 는 하위 시퀀스 (
j
아래
i
음수 의 첫 번 째 하 표 가 되 기 시작 하 다.그래서
i
추진 하 다
j+1
안전 합 니 다. 최 적 화 를 놓 치지 않 습 니 다.
주의 하 는 것 은 a [j] 로 끝 나 는 특정한 서열 과 마이너스 가 있 으 면 이 서열 중의 그 어떠한 숫자 도 a [j] 뒤의 수 와 형 성 된 가장 큰 서브 서열 의 시작 이 될 수 없 음 을 나타 낸다. 그러나 a [j] 앞의 특정한 서열 이 최대 서열 이 아니 라 는 것 을 나타 내지 않 는 다. 즉, 가장 큰 서브 서열 이 a [j] 앞 에 있 는 지 a [j] 뒤에 있 는 지 확인 할 수 없다 는 것 이다.즉, 최대 하위 서열 의 위 치 를 구 할 수 없다.그러나 max Sum 의 값 이 현재 가장 큰 하위 서열 과
이 알고리즘 은 또 하 나 는 데 이 터 를 한 번 만 스 캔 한 다 는 것 이다.
a[j]
읽 기 처리 되면 더 이상 기억 할 필요 없어.그것 은 하나 이다.
온라인 알고리즘.