매일 한 문제 [1] - 배열 의 하위 배열 의 합 의 최대 치 를 구하 세 요.

제목: 성형 배열 을 입력 하 십시오. 배열 에는 양수 도 있 고 마이너스 도 있 습 니 다.배열 에서 연속 되 는 하나 또는 여러 개의 정수 가 하나의 키 배열 을 구성 하고 모든 하위 배열 은 하나의 합 이 있다.모든 하위 배열 의 합 의 최대 치 를 구하 십시오.시간 복잡 도 를 O (n) 로 요구 합 니 다.
예 를 들 어 입력 한 배열 은 1, - 2, 3, 10, - 4, 7, 2, - 5 이 고 가장 큰 하위 배열 은 3, 10, - 4, 7, 2 이기 때문에 이 하위 배열 의 것 과 18 로 출력 된다.
이 문 제 는 프로 그래 밍 100 문제 와 프로 그래 밍 의 아름다움 에 상응하는 해답 이 있 으 며, 아래 에 자신의 전체 코드 를 붙인다
#include 
using namespace std;
int MaxSum(int a[],int n){
	int max=a[0];
	int tmpMax=a[0];
	for(int i=1;imax)
			max=tmpMax;
	}
	return max;
}
int main(){
	int a[8]={1,-2,3,10,-4,7,2,-5};
	int sumMaxSubArray=MaxSum(a,8);
	cout<

이것 은 프로 그래 밍 의 아름다움 알고리즘 의 완전한 실현 이다
#include 
using namespace std;
int MaxSum(int a[],int n){
	int nStart=a[n-1];
	int nAll=a[n-1];
	for(int i=n-2;i>=0;i--){
		if(nStart<0)
			nStart=0;
		nStart+=a[i];
		if(nStart>nAll)
			nAll=nStart;
	}
	return nAll;
}
int main(){
	int a[8]={1,-2,3,10,-4,7,2,-5};
	int sumMaxSubArray=MaxSum(a,8);
	cout<

좋은 웹페이지 즐겨찾기