[동적 기획] 최대 서브 시퀀스
1756 단어 데이터 구조
2. 주어진 서열 에서 연속 최대 하위 서열 을 찾 아 하위 서열 의 적 을 최대 치 로 만족 시 키 고 이 최대 치 를 되 돌려 줍 니 다.
생각:
첫 번 째 문 제 는 먼저 변수 curMax 를 신청 하여 현재 하위 서열 의 누적 과 초기 화 를 0 으로 표시 합 니 다. res 는 현재 모든 하위 서열 과 최대 치 를 표시 하고 최소 값 INT 로 초기 화 합 니 다.MIN。시퀀스 에서 데이터 x 를 순서대로 읽 고 curMax > 0 이면 읽 은 데 이 터 를 현재 시퀀스 에 추가 합 니 다. curMax = curMax + x;만약 curMax < 0 이 라면 이전의 서열 을 버 리 고 현재 읽 은 데 이 터 를 다시 시작 하여 새로운 서열 의 누적 과 를 계산 합 니 다. 이때 curMax = x;매번 curMax 를 업데이트 할 때마다 curMax 와 res 의 크기 를 판단 해 야 합 니 다. curMax > res 가 있 으 면 res 를 curMax 로 업데이트 합 니 다.
두 번 째 문제 의 사고방식 은 비슷 하 다. 하나의 변 수 를 신청 하면 curMax 는 현재 하위 서열 의 누적 적 을 나타 내 고 1 로 초기 화 하 며 res 는 현재 모든 하위 서열 의 최대 치 를 나타 낸다.다른 것 은 새로운 하위 서열 이 현재 곱 하기 0 이 나 타 났 을 때 입 니 다. 또한 주의해 야 할 것 은 모든 하위 서열 의 곱 하기 를 확보 하기 위해 서 는 정렬 과 역순 이 두 번 주어진 서열 을 옮 겨 다 녀 야 합 니 다.
코드 는 다음 과 같 습 니 다:
첫 번 째 문제:
class Solution {
public:
int maxSubArray(vector& nums) {
int len=nums.size();
int curMax=0,res=INT_MIN;
for(int i=0;i0?(curMax+nums[i]):nums[i];
if(curMax>res)
res = curMax;
}
return res;
}
}; 두 번 째 문제:
class Solution {
public:
int maxProduct(vector& nums) {
int len=nums.size();
long long curMax=1,res=INT_MIN;
for(int i=0;ires) res = curMax;
if(curMax==0) curMax=1;
}
curMax=1;
for(int i=len-1;i>=0;i--){
curMax=curMax*nums[i];
if(curMax>res) res = curMax;
if(curMax==0) curMax=1;
}
return res;
}
}; 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
