배열 에서 가장 대련 속 자 서열 의 합 을 구하 다.
4394 단어 배열
참조 링크: http://blog.csdn.net/butwang/article/details/4691974
사고: 0 ~ k - 1 공 k 개 요소 중에서 최대 와 MaxAll [k - 1] 을 알 고 있다 면 0 ~ k 공 k + 1 개 요소 의 MaxAll [k] 을 어떻게 구 합 니까?만약 에 앞의 k 개 요소 의 최대 와 하위 서열 이 a [k - 1] 을 포함한다 면 MaxAll [k] = max (MaxAll [k - 1] + a [k], a [k]) 를 쉽게 알 수 있 습 니 다.그럼 앞의 k 개 요소 의 최대 와 하위 서열 이 a [k - 1] 를 포함 하지 않 는 다 면?배열 뒤에 요 소 를 추가 하면 배열 의 마지막 체면 서열 의 합 을 바 꿀 수 있 기 때문에 MaxAll [k] = max (MaxAll [k - 1], MaxAll [k - 1] + a [k], a [k]).EndMax [k - 1] 을 앞의 k 개 요소 에 a [k - 1] 의 최대 하위 서열 과 포함 하도록 정의 합 니 다.전달 공식 은 다음 과 같다.
EndMax[k] = max(EndMax[k-1] + a[k], a[k])
MaxAll[k] = max(MaxAll[k-1], EndMax[k])
이 를 통 해 알 수 있 듯 이 두 개의 배열 을 사용 할 필요 가 없고 두 개의 변 수 를 사용 하여 MaxAll [k] 과 EndMax [k] 를 대체 할 수 있다.
코드:
1 package algorithm; 2 3 public class maxSubSum { 4 // 5 public static void main(String[] args) { 6 int a[] = { -3, 3, -1, 4, -2, -1 }; 7 8 int AllMax = a[0]; 9 int EndMax = a[0]; 10 11 int AllMaxStart = 0, AllMaxEnd = 0, EndMaxStart = 0, EndMaxEnd = 0; 12 13 for (int i = 1; i < a.length; i++) { 14 if (EndMax + a[i] > a[i]) { 15 EndMax = EndMax + a[i]; 16 EndMaxEnd = i; 17 } else { 18 EndMax = a[i]; 19 EndMaxStart = i; 20 EndMaxEnd = i; 21 } 22 23 if (EndMax > AllMax) { 24 AllMax = EndMax; 25 AllMaxStart = EndMaxStart; 26 AllMaxEnd = EndMaxEnd; 27 } 28 } 29 30 System.out.println("MaxValue: "+AllMax+", Start: "+AllMaxStart+", End: "+AllMaxEnd); 31 } 32 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
PHP 배열에서 요소의 값이 최대 값인 키 이름을 가져옵니다.Qiita 에 " "@ PHP 매뉴얼 데이터 최대값이 나타나는 순서대로 획득 결과 키를 정렬한 후 가져오기 결과 @ paiza.IO PHP v5.6.40, v7.1.33, v7.4.4 " "@ StackOverflo...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
