leetcode 의 연속 하위 배열 의 최대 곱 하기
예시 2: 입력: [- 2, 0, - 1] 출력: 0 해석: 결 과 는 2 가 될 수 없습니다. [- 2, - 1] 은 하위 그룹 이 아니 기 때 문 입 니 다.사고방식: 곱셈 의 최대 치 를 구하 라. 예 를 들 어 음수 가 나타 나 기 때문에 하나의 양수 곱 하기 음 수 는 음수 가 된다. 즉, 최대 치 곱 하기 음 수 는 최소 치가 된다.마찬가지 로 최소 치 에 음 수 를 곱 하면 최대 치가 될 수도 있다.최대 치 나 최소 치 곱 하기 0 도 모두 0 이 되 었 다.따라서 우 리 는 두 개의 동적 계획 배열, f [i] 로 i 까지 연속 서브 배열 의 최대 곱 하기 를 저장 합 니 다.g [i] j 까지 저장 하고 연속 서브 배열 의 최소 곱 하기.f[i]=max(nums[i]*f[i-1],nums[i],nums[i]*g[i-1]) g[i]=min(nums[i]*f[i-1],nums[i],nums[i]*g[i-1])
python 해법:
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums:return 0
N=len(nums)
f=[0]*N
g=[0]*N
f[0]=g[0]=res=nums[0]
for i in range(1,N):
f[i]=max(f[i-1]*nums[i],nums[i],g[i-1]*nums[i])
g[i]=min(f[i-1]*nums[i],nums[i],g[i-1]*nums[i])
res=max(res,f[i])
return res
자바 해법:
class Solution {
public int maxProduct(int[] nums) {
if (nums ==null || nums.length==0) return 0;
int res=nums[0];
int pre_max=nums[0];
int pre_min=nums[0];
for (int i=1;i<nums.length;i++){
int cur_max=Math.max(Math.max(pre_max*nums[i],pre_min*nums[i]),nums[i]);
int cur_min=Math.min(Math.min(pre_max*nums[i],pre_min*nums[i]),nums[i]);
res=Math.max(res,cur_max);
pre_max=cur_max;
pre_min=cur_min;
}
return res;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
