[LeetCode] 53. Maximum Subarray

시험기간인데, 발등에 불을 끄느라 최근에 문제를 거의 못 풀었다.
알고리즘 공부하다가 Maximum Subarray 내용을 배웠고 똑같은 문제가 있길래 풀어보았다.

내가 푼 방법은 배열을 탐색하면서 해당지점의 값을 A[i], i이전까지 더한 값을 sum 을 이용하여
i번째 수를 더한 상황, i번째에서 새로 시작하는 상황을 비교한다.
즉 sum+A[i] 와 A[i]를 비교하여 더 큰 값으로 최신화 시킨다.

prefixSum과 prefixMin을 이용해 푸는 방법도 있는데, 이건 코드가 어디서 틀렸는지 방법은 아는데 답을 빨리 못내서 보류했다.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
        int max = -1000000000, answer = -1000000000;
        for(int i=0; i<nums.size(); i++){
            if(nums[i]+max > nums[i]){
                max = nums[i]+max;
            }
            else{
                max = nums[i];
            }

            if(answer<max){
                answer = max;
            }
            
        }
        return answer;
    }
};