문제를 푸다Maximum Subarray

제목 설명
제목은 53.Maximum Subarray, 연속 하위 시퀀스의 최대 및 최대를 구합니다.난이도는 이지!
2. 나의 해답
Easy의 제목을 뜻밖에도 만들지 못했다.
나중에 dp 방법을 사용했는데 그 중에서 dp[i]는 i번째 요소로 끝나는 가장 큰 합을 나타냈다.dp[i] = nums[i] > nums[i]+dp[i-1] ? nums[i] : nums[i]+dp[i-1];
그리고 가장 큰 dp를 구하면 됩니다.사고방식을 알고 실현하는 것은 매우 간단하지만 문제는 동태적인 계획 위에 생각하지 않았다는 것이다.

#include
#include

using namespace std;
class Solution{
public:
    int maxSubArray(vector& nums) {
        int len=nums.size();
        vector dp;
        dp.resize(len);
        //  i          
        dp[0] = nums[0];
        int max = dp[0];
        for(int i=1;i nums[i]+dp[i-1] ? nums[i] : nums[i]+dp[i-1];
            max = max > dp[i] ? max : dp[i];
        } 
        
        return max;
    }
};
int main(){
    Solution s;

    vector m;
    m = {-2,1,-3,4,-1,2,1,-5,4};
    cout<

성능이 의외로 괜찮다. 공간이 복잡해서 최적화할 수 있다. dp는nums를 복용한다. 역시 됐어. 가독성이 좋지 않다.

Runtime: 4 ms, faster than 98.55% of C++ online submissions for Maximum Subarray.
Memory Usage: 9.4 MB, less than 17.65% of C++ online submissions for Maximum Subarray.

3. 최적화
제목은 분치 알고리즘으로 분치하라고 했다.생각해 보니'2점 찾기'와 유사할 것 같다.아니요, 대신의 실현을 봤어요.

class Solution{
public:
    //divide & conquer approach
    int maxSubArray(vector& nums) {
        return maxSubArrayPart(nums,0,nums.size()-1);
    }
private:
    int maxSubArrayPart(vector& nums,int left,int right){
        if(left==right){
            return nums[left];
        }
        int mid = (left+right) / 2;
        return max(maxSubArrayPart(nums,left,mid),
            max(maxSubArrayPart(nums,mid+1,right),maxSubArrayAll(nums,left,mid,right)));
    }
    
    //       
    int maxSubArrayAll(vector& nums,int left,int mid,int right){
        int leftSum = INT_MIN;
        int sum=0;
        for(int i=mid;i>=left;i--){
            sum += nums[i];
            if(sum>leftSum) leftSum=sum;
        }
        
        sum=0;
        int rightSum= INT_MIN;
        for(int i=mid+1;i<=right;i++){
            sum += nums[i];
            if(sum>rightSum) rightSum=sum;
        }
        
        return leftSum+rightSum;
    }
};

성능:

Runtime: 8 ms, faster than 74.25% of C++ online submissions for Maximum Subarray.
Memory Usage: 9.4 MB, less than 33.33% of C++ online submissions for Maximum Subarray.