문제 설명 : n 요소가있는 배열,이 n 요소는 양수 또는 음수 일 수 있습니다. 가장 큰 서브 어레이의 합을 찾으십시오.
방법 1 : 무차별 인력 방법
아이디어 : 가장 쉽고 가장 쉬운 방법은 모든 서브 사업을 찾은 다음 모든 서브 배열의 합을 찾은 다음 모든 서브 배열의 합으로 최대 값을 얻는 것입니다.
/ *** 메소드 1 (Brute Force Method) : 두 루프에서 최대 서브 어레이의 합을 찾으십시오*/ public static int maxsubarray1 (int [] a) {int i, j; int thissum = 0; int maxsum = 0; for (i = 0; i <a.length; i ++) {thissum = a [i]; for (j = i+1; j <a.length; j ++) {thissum+= a [j]; if (thissum> maxsum) {maxsum = this sum; }} return maxsum; }방법 2 : 최적화 된 동적 프로그래밍
아이디어 : 먼저, 배열의 마지막 요소 A [N-1]와 가장 큰 서브 어레이 사이의 관계에 따르면 다음 세 가지 상황으로 나눌 수 있습니다.
1) 최대 서브 어레이는 [N-1], 즉 [N-1]으로 끝납니다.
2) [N-1] 단독은 가장 큰 서브 어레이를 형성합니다.
3) 최대 서브 어레이에는 [N-1]가 포함되지 않으므로 [1, ..., N-1]의 최대 서브 어레이를 찾는 것은 [1, ..., n-2]의 최대 서브 어레이를 찾는 것으로 변환 될 수 있습니다.
위의 분석을 통해 우리는 다음과 같은 결론을 도출 할 수 있습니다. 가장 큰 배열 (a [0], ... a [i-1])의 합이 모든 [i-1]로 계산되었으며 (a [0], ... a [i-1])에서 [I-1]의 가장 큰 배열의 합은 끝 [i-1]으로 계산된다고 가정합니다.
그런 다음 다음 관계를 얻을 수 있습니다 : 모든 [i-1] = max {a [i-1], 종료 [I-1], 모든 [i-1]}. 이 공식과 동적 프로그래밍 아이디어를 사용하여 문제를 해결하십시오. (코드는 또한 시작 위치 및 종료 위치의 문제를 해결합니다)
/*** 메소드 2 : 최적화 된 동적 프로그래밍 방법* Nend는 순서대로 [i]에 배열을 추가 한 다음 [i]와 더 큰 것을 저장함으로써 얻은 다음 더 큰 것을 저장함으로써 얻어집니다. "이전 숫자가 [i]*에 추가되면 [i]*만큼 크지 않기 때문에 이전 숫자는 가장 큰 서브 array에 기여하지 않을 것입니다. public static int max (int m, int n) {return m> n? m : n;} public static int maxsubarray2 (int [] a) {int nall = a [0]; // n numeric 어레이의 최대 서브 어레이의 합은 n numeric 어레이의 서브 어레이의 합을 포함합니다. nend = nall = max (nend, nall); maxsum = integer.min_value; int nsum = 0; int nstart = 0; for (int i = 0; i <a.length; i ++) {if (nsum <0) {nsum = a [i]; nstart = i; } else {nsum+= a [i]; } if (nsum> maxsum) {maxsum = nsum; 시작 = nstart; 끝 = i; }} return maxsum; }위는이 기사의 모든 내용입니다. 이 기사의 내용이 모든 사람의 연구 나 업무에 도움이되기를 바랍니다. 또한 wulin.com을 더 지원하기를 바랍니다!