데이터 구조 와 알고리즘 디자인 주제 의 - 하위 배열 과 최대 값 구하 기
1465 단어 데이터 구조
성형 배열 을 입력 하 십시오. 배열 에는 양수 도 있 고 마이너스 도 있 습 니 다.
배열 에서 연속 되 는 하나 또는 여러 개의 정수 가 하나의 키 배열 을 구성 하고 모든 하위 배열 은 하나의 합 이 있다.
모든 하위 배열 의 합 의 최대 치 를 구하 십시오.
예 를 들 어 입력 한 배열 은 1, - 2, 3, 10, - 4, 7, 2, - 5 와 가장 큰 하위 배열 은 3, 10, - 4, 7, 2 이다.
따라서 이 하위 배열 과 18 로 출력 합 니 다.
첫 번 째 방법:
쉽게 생각 나 는 것 은 이중 순환 을 사용 하 는 것 이다.
1 층 은 하위 배열 의 시작 위 치 를 찾 습 니 다: i
2 층 은 하위 배열 의 끝 위 치 를 찾 습 니 다: j
코드 는 다음 과 같 습 니 다:
public static void findMaxSubArySum2(){
//sum
int sum = 0;
//max
int max = 0;
//
int startPos = 0;
//
int endPos = 0;
int[] array = {-1,2,-3,12,-5,-1,9,-2};
for(int i=0;i<array.length;i++){
sum = 0;//
for(int j=i;j<array.length;j++){
sum += array[j];
// ， ， max
if(sum > max){
max = sum;
startPos = i;//
endPos = j+1;//
}
}
}
System.out.println("Max:"+max);
System.out.println("startPos:"+startPos+",endPos:"+(endPos-1));
}시간 복잡 도가 N * N 이면 최 적 화 된 방안 은 없 을 까?답 은 긍정 적 이다.
두 번 째 방법:
우리 가 정 수 를 더 하면 증가 한 다 는 것 을 쉽게 이해 할 수 있다.우리 가 마이너스 하 나 를 더 하면 줄 어 들 것 이다.만약 현재 얻 은 것 과 마이너스 라면, 이것 은
다음 누적 에 서 는 버 리 고 다시 0 으로 해 야 한다. 그렇지 않 으 면 이 음 수 는 다음 과 같은 합 을 줄 일 것 이다.
이러한 사고방식 을 바탕 으로 우 리 는 다음 과 같은 코드 를 쓸 수 있다.
4. 567913. 이렇게 하면 우 리 는 많은 최적화 되 었 고 시간 복잡 도 는 N 이라는 것 을 볼 수 있다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
