왜이 탐욕스러운 알고리즘이 효과가 있습니까?

는 시퀀스 S +와 주어 - 초기 값 0을 가진 변수 x에 각각 +1 -1 동작을 나타내는 문자, X는 임의의 달성 할 수있는 값의 최대 범위를 찾을 s의 서브 시퀀스.

예 :

S = + - + - + + ---- (4)의 최대 범위이다 이어질 것이다 +, X = 0

서브 시퀀스. x는 최대 값 1과 최소값 -3을가집니다.
count_minus = #occurrences of - character 
count_plus = #occurences of + character 
return max(count_minus, count_plus) 
왜이 작업을 수행 다음과 같이

의사 코드에서이 알고리즘에 대한 해결책은 무엇입니까?

출처

2017-10-20 Jay

모든 긍정적 인 부분을 제거하면 range=#negatives의 경우 max=0 및 min=-#negatives이됩니다. 마찬가지로 음화를 제거합니다. 정말로 더 좋아질 수는 없습니다.

출처

2017-10-20 02:06:20 MFisherKDX

답장을 보내 주셔서 감사합니다. 그러나 내가 이해하지 못했던 것은 올바른 서브 시퀀스에 준 예제에서 포지티브와 네거티브가 모두 있다는 것입니다. – Jay

예. * a * 최대 서브 시퀀스는 아니지만 * 유일한 * 최대 서브 시퀀스는 아닙니다. '+ ----'도 최대 시퀀스입니다. (또한 범위에 대해 + 1과 -3 = 4). '----'는 또한 최대 서브 시퀀스 (range = 4의 경우 0과 -4)입니다. #neg> #pos라고 가정합니다. 모든 pos를 제거하면'range = # neg'가됩니다. 그럼, #pos <# neg에 유도에 의해, 다른 하위 서열에는 더 큰 범위가 없다고 주장합니다. 긍정적 인 부분을 추가하십시오. 범위에 영향을 미치기 전에 네거티브 수가 <= 이전에 양수 인 위치에 추가해야합니다. 하지만 긍정적 인 것보다 많은 네거티브가 있기 때문에 결국에는 도움이되지 않습니다. – MFisherKDX

왜이 탐욕스러운 알고리즘이 효과가 있습니까?

답변

관련 문제