[C++][leetcode] Maximum Subarray :: seoftware

문제

 

 

접근방법

 

다이나믹 프로그래밍을 사용하려고 했는데 굳이 새로운 배열을 만들 필요는 없을것 같아서 max 값을 계속 업데이트 해주는 방식으로 접근!

 

소스코드

 

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max = 0; bool all_negative = true;
        for(int i = 0; i<nums.size();i++){
            if(nums[i] > 0){
                int tmp = 0;
                all_negative = false;
                for(int j = i; j<nums.size(); j++){
                    tmp += nums[j];
                    if(tmp > max) max = tmp;
                }
            }
        }
        if(all_negative) {
            max = nums[0];
            for(int i : nums){
                if(max < i) max = i;
            }
        }
        return max;
    }
};

 

빨리 풀라고 시작이 양수인 것만 subarray의 시작이 되도록 조건문을 걸어놨는데..

모든 수가 음수인 경우를 생각을 못 했다. 그래서 for문 아래에 if문으로 모든 원소가 음수인 경우를 따로 처리해줬다.