최소 합> 0

Question

최소 합계를 찾아, 숫자의 배열을 지정해 및 부분 배열의 길이 될 수 없습니다 0

나는 kadane의 알고리즘을 사용할 수 있습니다 알고 있지만 문제는 그 배열의 길이가해야 필요 따라서 배열의 모든 요소가 양수인 경우 구현할 수 없습니다. -5, -4, 5 : 2, 5, 3, 8, 4, 최소 합은 또한 같은 통상의 어레이에서 작동하는 2

이다 : 다음 배열 주어진 예

, , -1, 2, 최소 합계는 -9 (처음 두 요소의 합계)

어떻게해야합니까?

이

while (N--) { 
    scanf("%i", &num); 

    localmx += num; 
    if (localmx > 0) localmx = 0; 
    if (localmx < mx) mx = localmx; 
} 

Answer 1

그냥 카데나의 알고리즘을 사용하고, 대답은 빈 부분 배열 인 경우, 대신 배열의 최소 요소를 찾을 수 :

여기 내 구현입니다.