제3 장 알고리즘 실천 보고서

7-2 최대 하위 세그먼트 와 (40 분 하 다
 
n 개의 정수 (음수 일 수 있 음) 로 구 성 된 서열 a [1], a [2], a [3],.주어진 정수 가 모두 마이너스 일 때 하위 세그먼트 와 0 을 정의 합 니 다.
알고리즘 의 시간 복잡 도 를 O (n) 로 요구 합 니 다.
입력 형식:
두 줄 입력:
첫 번 째 줄 은 n 값 (1 < = n < = 10000) 입 니 다.
두 번 째 줄 은 n 개의 정수 이다.
출력 형식:
출력 최대 하위 세그먼트 와.
입력 예시:
여기에 입력 을 입력 하 십시오. 예 를 들 어:

6
-2 11 -4 13 -5 -2

출력 예시:
여기에 해당 하 는 출력 을 보 여 줍 니 다. 예 를 들 어:
20
 
  ：
#include
using namespace std;
int findMax(int a[],int n){
    int sum = 0;
    int b = 0;
    for(int i = 0 ;i < n; i++){
        if(b>0){
            b =b + a[i];
        }else{
            b = a[i];
        }
        
        if(b>sum) sum=b;
    }
    return sum;
}
int main(){
    int n;
    cin>>n;
    int a[10001];
    for(int i=0;i
        cin>>a[i];
    }
    cout<
    return 0;
}
 
문제 풀이 방향: 필드 가 연속 되 는 것 을 요구 하지 않 기 때문에 이 문 제 는 어렵 지 않 습 니 다. 하나의 수 와 다른 수 (max) 를 설정 하고 0 으로 초기 화 하 며 a [0] 부터 계속 추가 하고 소득 이 마이너스 이면 배열 의 다음 수 를 직접 할당 합 니 다. 그렇지 않 으 면 계속 중첩 합 니 다. 만약 에 이 수가 max 보다 크 면 max 에 할당 합 니 다.