누군가이 알고리즘을 C++로 설명 할 수 있습니까? 사람이 어떻게 알고리즘 작품을 설명 할 수있는 경우

Question

이차 최대 연속 서브 합 알고리즘

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

궁금 해서요? 나는 for 루프를 잘한다. 나는 중첩 된 것들에 대해서 나쁘다. "thisSum"은 0 번 라인이 실행될 때마다 항상 0입니까? 아니면 정적입니까?

대단히 감사합니다! 알고리즘을 이해하기가 정말로 힘듭니다. 제발 도와주세요! 나는 정말로 시간과 노력에 감사한다.

Answer 1

바깥 쪽 for 루프가 바뀔 때마다 바깥 쪽 루프의 첫 번째 줄에있는 =0 때문에이 합계가 0으로 다시 설정됩니다.

i, j 및 thisSum을 내부 루프에 인쇄하여 변경 방법을 볼 수 있도록 수정하는 것이 좋습니다.

Answer 2

외부 루프는 벡터 a의 모든 요소를 ​​반복합니다. 각 반복에서 i은 현재 요소의 인덱스가되고 thisSum을 0으로 다시 설정 한 다음 내부 루프를 실행합니다.

내부 루프는 i부터 시작하는 모든 요소를 ​​반복합니다. 각 반복에서 j은 현재 요소의 인덱스가됩니다. 그런 다음 이들 요소의 합을 thisSum에 계산합니다.

외부 루프는 maxSum을 이미 포함 된 것보다 높은 경우 thisSum으로 바꿉니다.

벡터가 포함 그렇다면 : 외부 루프

1 7 -10 2 4 

연속 반복은 thisSum의 다음 값을 계산한다 :

1 + 7 + -10 + 2 + 4 = 4 
7 + -10 + 2 + 4 = 3 
-10 + 2 + 4 = -4 
2 + 4 = 6 
4 = 4 

첫번째 반복 그것은 4에 maxSum를 설정한다. 두 번째 및 세 번째 반복 후에는 thisSum > maxSum이 false가되므로 변경되지 않습니다. 네 번째 반복에서 6 > 4이므로 maxSum을 6으로 설정합니다. 마지막 반복은 변경되지 않습니다. 마지막으로 6을 반환합니다.

Answer 3

예 A는 = [1, 2, 3, 4, 5]

j는 i 값에서 시작하므로 먼저 0 등을 1 다음 2를 시작한다. 따라서이 두 번째 내부 루프는 외부 루프가 증가 할 때마다 더 작습니다.

thisSum은 정적이 아니므로 매번 0으로 재설정됩니다. 그럴 경우 정적이라고 표시됩니다.

기본적으로이 알고리즘에서는 외부 루프를 사용하여 '시작 인덱스'를 앞쪽으로 밀어 내 루프를 사용하여 실제로 배열/벡터의 모든 요소를 ​​함께 추가합니다.

따라서 위의 예를 들어 내부 루프의 실행은 다음과 같습니다 도움이

Execution 1: 1 + 2 + 3 + 4 + 5 
Execution 2: 2 + 3 + 4 + 5 
Execution 3: 3 + 4 + 5 
Execution 4: 4 + 5 
Execution 5: 5 

희망.코드 라인 (8)에서

Answer 4

thisSum는

루프 I의 시작 부분에서 리셋하지만 thisSum는 루프 J의 루프 J에 배열 [η] 요소를 추가로 유지하다.

---

일반적으로 나는 루프의 작동 방식을 이해하기 위해 값을 대체하고 값을 사용합니다.

스텝에 의해 최대 합을 얻기 위해 시도되고, 벡터 A는 3 개 INT 소자 (10)를 보유지지 -20,100

따라서

a.size() = 3

//maxSum is initialized in the function 
int maxSum = 0; 

//Start First i loop 
int i = 0; i < 3; 
int thisSum = 0; 

int j = i = 0; j < 3; 
thisSum += a[0]; 
//thisSum = 10 
//10 > 0 
if (thisSum > maxSum) maxSum = thisSum = 10; 
int j = i = 1; j < 3; 
thisSum += a[1]; 
//thisSum = -10 
// -10 not > 10 
int j = i = 2; j < 3; 
thisSum += a[2]; 
//thisSum = 90 
//90 > 10 
if (thisSum > maxSum) maxSum = thisSum = 90; 
//End First i loop 

//Start 2nd i loop 
int i = 1; i < 3; 
int thisSum = 0; 

int j = i = 1; j < 3; 
thisSum += a[1]; 
//thisSum = -20 
//-20 not > 90 
int j = i = 2; j < 3; 
thisSum += a[2]; 
//thisSum = 80 
//80 not > 90 
//End 2nd i loop 

//Start 3rd i loop 
int i = 2; i < 3; 
int thisSum = 0; 

int j = i = 2; j < 3; 
thisSum += a[2]; 
//thisSum = 100 
//100 > 90 
if (thisSum > maxSum) maxSum = thisSum = 100; 
//End 3rd i loop 

//return 100 
//return maxSum 

함수의 개념하자 가장 작은 인덱스 요소에서 가장 큰 인덱스 인수로 항목을 제거하십시오.

1 루프 I : maxSum = 90

두번째 루프는 내가 : maxSum은 = 90 내가

3 루프 (10 제거) : maxSum은 = 100 (10 제거, -20) 그냥