최대 하위 서열과 곱셈 최대 하위 그룹
1684 단어 동적 기획
최대 하위 순서 및:https://leetcode-cn.com/problems/maximum-subarray/
승적 최대 하위 배열:https://leetcode-cn.com/problems/maximum-product-subarray/
문제 해결 방법:
동적 기획 문제는 세 가지 조건을 만족시켜야 한다. 첫째는 최우수자 구조이고, 둘째는 자 문제가 중첩되고, 셋째는 후효성이 없다.가장 어려운 것은 상태 이동 방정식을 찾는 것이다.
두 문제의 상태 이동 방정식의 관건은 i번째 요소로 끝나는 최대치를 이해하는 데 있다.
예를 들면 다음과 같습니다.
테스트 그룹은 [1,7,-3,4]
index=0 즉 원소1로 끝나는 하위 서열과 가장 큰 서열은 1이다(1로 끝나는 하위 서열이 하나밖에 없기 때문이다[1])
index=1 즉 원소7로 끝나는 서열과 가장 큰 서열은 얼마나 됩니까?원소 7로 끝나면 하위 서열은 반드시 7을 포함하고 최대값은 두 하위 서열에서 나올 수 있다
1. 그 앞의 원소와 연속하여 서열을 구성하려면 서열에는 반드시 그 앞의 원소인 1이 포함되고 index=i-1로 끝나는 가장 큰 원소는 우리가 구한 max[i-1]이기 때문에 max[i]=max[i-1]+nums[i];
2. 앞의 원소와 서열을 구성하지 않을 수도 있고 원소 자체가 서열이 되면 max[i]=nums[i];
따라서 max[i]=MAX(max[i-1]+nums[i],nums[i]);
class Solution {
public int maxSubArray(int[] nums) {
int ans = nums[0];
int sum = 0;
for(int num: nums) {
sum = Math.max(sum+num, num);
ans = Math.max(ans, sum);
}
return ans;
}
}class Solution {
public int maxProduct(int[] nums) {
int len = nums.length;
if(len == 0){
return 0;
}
int res = Integer.MIN_VALUE;
int max_i = 1;
int min_i = 1;
for(int i = 0 ; i < len; i++){
if(nums[i] < 0){
int temp = max_i;
max_i = min_i;
min_i = temp;
}
max_i = Math.max(max_i*nums[i], nums[i]);
min_i = Math.min(min_i*nums[i], nums[i]);
res = Math.max(max_i, res);
}
return res;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
