최대 서브 시퀀스 와 네 가지 방식

최대 하위 시퀀스 의 문제 설명:원 배열 을 지정 하여 연속 하위 배열 의 최대 합 을 구하 십시오.
이전에 총 결 한 적 이 있 지만 다른 책 을 볼 때 대부분의 책의 첫 번 째 범례 는 가장 큰 하위 서열 과 그 렇 기 때문에 전체 판 이다.
1.궁 거 식 의 예 를 들 어 가능 한 모든 것 을 선택 합 니 다.
시간 복잡 도:O(n^3)
분석:for 순환 을 사용 하여 끼 워 넣 고 모든 가능성 을 예 로 들 어 계산 한 다음 에 가장 큰 값 을 선택 합 니 다.
코드 는 다음 과 같 습 니 다:

package code;

import java.util.Scanner;

public class Max1 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int k=sc.nextInt();
		int[] arr=new int[k];
		for(int i=0;iMaxSum) {
					MaxSum=ThisSum;
				}
			}
		}
		return MaxSum;
	}
}

2.이전 방법 에 비해 발전
시간 복잡 도:Q(n^2)
분석:이전 방법 에 비해 FOR 순환 으로 인 한 중복 계산 을 줄 이려 고 합 니 다.
코드 는 다음 과 같 습 니 다:

package code;

import java.util.Scanner;

public class Max2 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int k=sc.nextInt();
		int[] arr=new int[k];
		for(int i=0;iMaxSum) {
					MaxSum=ThisSum;
				}
			}
		}
		return MaxSum;
	}
}

3.재 귀적 인 분할 정책 사용
시간 복잡 도:O(nlogn)
분석:문 제 를 대체적으로 같은 두 개의 하위 문제 로 나 눈 다음 에 그들 에 게 재 귀적 으로 해결 하 는 것 은'부분'이다.그리고'치료 부분'은 두 개의 문 제 를 합 쳐 서 다시 상의 할 수 있 는 부가 작업 을 해서 전체 문 제 를 해결 하 는 것 이다.데이터 구조 와 알고리즘 분석 C 언어 설명>
코드 는 다음 과 같 습 니 다:

package code;

import java.util.Scanner;

public class Max3 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int k=sc.nextInt();
		int[] arr=new int[k];
		for(int i=0;i=left;i--) {
			 ThisLeftSum+=arr[i];
			 if(ThisLeftSum>MaxCenterLeftSum) {
				 MaxCenterLeftSum=ThisLeftSum;
			 }
		 }
		 
		 ThisRightSum=0;
		 MaxCenterRightSum=0;
		 for(int j=center+1;j<=right;j++) {
			 ThisRightSum+=arr[j];
			 if(ThisRightSum>MaxCenterRightSum) {
				 MaxCenterRightSum=ThisRightSum;
			 }
		 }
		 
		 return Max(MaxLeftSum,MaxRightSum,MaxCenterLeftSum+MaxCenterRightSum);
	}
	public static int Max(int a,int b,int c) {
		int max=0;
		if(a

4.온라인 알고리즘(스캐닝 법)
시간 복잡 도:O(n)
분석:데 이 터 를 한 번 만 스 캔 하고 arr[i]가 읽 히 고 판단 한 후에 이 데 이 터 를 사용 하지 않 기 때문에 이 데 이 터 를 기억 할 필요 가 없습니다.
코드 는 다음 과 같 습 니 다:

package code;

import java.util.Scanner;

public class Max4 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int k=sc.nextInt();
		int[] arr=new int[k];
		for(int i=0;iMaxSum) {
				MaxSum=ThisSum;
			}else {
				if(ThisSum<0) {
					ThisSum=0;
				}
			}
		}
		return MaxSum;
}
}