[면접문제] 연속 서브그룹의 최대 합

1891 단어 배열면접 문제
제목.
하나의 정형수조가 있는데, 그 안의 원소는 정수와 음수가 있고, 하나 또는 연속된 여러 원소가 하나의 자수조를 구성하여 모든 자수조의 합의 최대치를 구한다.즉 연속 서브 그룹의 최대와 문제다.
분석하다.
이 문제는 보통 동태 기획을 사용하는데 면접에서 물어보는 것도 동태 기획을 고찰하는 것이다.f(i)는 i로 끝나는 하위 그룹의 최대 합을 나타낸다.이왕 i로 끝났으니 어디서부터 시작할까?j가 i의 왼쪽에 있는데 만약에 A[0]에서 A[j]까지의 합이 마이너스라면 f(i)는 j+1부터 시작해야 한다.그럼 f(i)의 추이 공식은 어떻게 계산합니까?f(i) = f(i-1) + A[i];조건은 f(i-1) > 0 f(i) = A[i]입니다.조건은 f(i-1)<=0이 요구하는 결과 ans는 모든 f(i)의 최대치와 같다.
코드
class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int len = array.size();
        if(len == 0)
            return 0;
        int k_sum = array.at(0);
        int max_sum = array.at(0);
        for(int i = 1; i < len; i++){
            if(k_sum < 0)
                k_sum = array.at(i);
            else
                k_sum += array.at(i);
            max_sum = max(k_sum, max_sum);
        }
        return max_sum;
    }
};
ubuntu 설치 node, pm2, nginx 등 응용 프로그램 (전단)
이전 버전의 Inkscape 파일을 Inkscape1.0으로 변환한 후 Display units에서 변경할 수 없는 문제 및 대응 방법

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage