우 객 당 솔 문제 의 최대 곱 하기
1139 단어 최대 곱 하기우 객 당 알고리즘
double 형식의 배열 arr 를 지정 합 니 다. 그 중의 요 소 는 마이너스 0 이 고 하위 배열 의 누적 곱 의 최대 곱 을 되 돌려 줍 니 다.예 를 들 어 arr = [- 2.5, 4, 0, 3, 0.5, 8, - 1], 하위 배열 [3, 0.5, 8] 의 누적 승 은 가장 큰 곱 하기 12 를 얻 을 수 있 기 때문에 12 로 돌아간다.
생각:
연속 서브 시퀀스 를 구 하 는 문 제 는 모두 앞의 i 개 요소 가 i + 1 개 요소 에 대한 추측 이다.
그러면 0 ~ ~ ~ ~ i ~ ~ ~ N - 1 중 0 ~ ~ ~ i 가운데 최대 치 는 Max, 최소 치 는 Min
그러면 i + 1 로 끝 나 는 서열 로 발생 하 는 최대 치 는 세 가지 상황 이 있 습 니 다.
1. Max * array [+ 1], 예 를 들 어 2 3 4
2. Min * array [i + 1], 예 를 들 어 - 2, 3 - 4
3、array[i+1] ,예 를 들 면 5. - 2, 3.
그래서 전역 에서 가장 큰 변 수 를 설정 합 니 다. 먼저 이 세 개의 크기 를 비교 한 다음 에 가장 큰 변수 와 전역 에서 가장 큰 변 수 를 비교 하고 크 면 교체 합 니 다.
코드:
public static double getMaxProduct(double[] arr)
{
double res = arr[0];
double max = arr[0];
double min =arr[0];
double maxTemp=0;
double minTemp=0
for(int i=1;i<arr.length;i++)
{
maxTemp = max * arr[i];
minTemp = min * arr[i];
max = Math.max(Math.max(maxTemp,minTemp),arr[i]);
min = Math.min(Math.min(maxTemp, minTemp),arr[i]);
res = Math.max(res, max);
}
return res;
}