Leetcode - 53. Maximum Subarray

문제

주어진 배열의 subarray 합중 가장 큰 합은? (subarray는 연속된 배열)

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

1. Constraints
 - 1 <= nums.length <= 10^5
 - -10^4 <= nums[i] <= 10^4
 - what is subarray? -> contiguous sub array.
 - dont't need to know exact range idices, only max sum.
2. Ideas
 - brute force way -> O(N^2)
 - two pointer?
 -2,1,-3,4,-1,2,1,-5,4
  |    | 
3. Test Cases
 - single (pos/neg)
 - all negative
 - zero
4. Coding

해결 O(N^2)

아이디어가 안떠올라서 N^2으로 풀었는데, 답은 맞았으나 Time Limit Exceeded됨.

nt maxSubArray(int* nums, int numsSize){
    int max = -10001, sum = 0;;
    for (int i = 0; i < numsSize; i++) {
        sum = 0;
        for (int j = i; j < numsSize; j++) {
            sum += nums[j];
            if (sum > max)
                max = sum;
        }
    }
    return max;
}

해결 O(N)

첨엔 이게 왜 되나 싶었음. sum이 음수가 될바에는 음수중 가장 큰값 하나만 max에 저장하는게 나음. 그래서 sum이 음수일때 0으로 갱신하고 max는 계속 가장 큰 음수하나의 값으로 갱신된다.

int maxSubArray(int* nums, int numsSize){
    int max = -10001, sum = 0;;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
        if (sum > max)
            max = sum;
        if (sum < 0)      // <-
            sum = 0;      // <-
    }
    return max;
}

해결 O(N)

22.7.20에 다시 푼 풀이. (다시 보니 LeapMotion이라는 회사에서 냈었던 테크니컬 스크리닝 문제였음)
범위 합을 계속 더하다가 sum이 0보다 작아지고 동시에 현재배열값이 sum보다 크다면 sum을 그 지점부터 다시 더해도됨.

#define max(a,b) (((a) > (b)) ? (a) : (b))
int maxSubArray(int* nums, int numsSize){
    int max = INT_MIN;
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        if (sum < 0 && nums[i] > sum)
            sum = 0;
        sum += nums[i];
        max = max(sum, max);
    }
    return max;
}

해결 O(N) 230127 다시풀어봄

위 O(N)해결책이 모두 동일한 알고리즘인데 아래 코드가 가장 직관적.
모든 sum값에대해서 max갱신, 단 값이 음수가 나오면 해당 값을 max 갱신하고 sum을 0으로 변경.
합이 음수가 아닌값을 처음 만나면 그 요소부터 새로 더하기를 시작 (max 갱신)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0;
        int maxsum  = nums[0];
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            maxsum = std::max(maxsum, sum);
            if (sum < 0)
                sum = 0;
        }
        return maxsum;
    }
};

해결 O(nlogn) divide & conquer

• 생각하는 프로그래밍 chap.8 참고 p149

• 왼쪽 절반에서 최대값, 오른쪽 절반에서 최대값, 그리고 가운데 값을 포함한 sub array에서의 최대값.

  • 이 세값을 비교해서 가장 큰값이 해당 범위에서의 최대값이 된다.
  • 이를 divide & conquer로 재귀적으로 반복,

• 구현시 실수한 부분

  • 재귀함수 내에서 left, right 로 범위가 제한되지만 0, size범위로 탐색함. (이거 예전에도 여러번 실수했었음)
  • 벡터를 함수 인자로 전달할때 & 레퍼런스로 보내야 스택오버플로우가 발생하지 않음. 그렇지 않으면 배열을 통째로 복사함. (앞으로 참고할것)

• 아주 흥미로운 풀이방법이었음!

class Solution {
public:
    int maxarr(vector<int> &nums, int left, int right) {
        if (left > right)
            return 0;
        if (left == right)
            return nums[left];
        
        /* find max sum expanding from mid to both side*/
        int mid = left + (right - left) / 2;
        int max_l = nums[mid];
        int l_sum = 0;
        for (int i = mid; i >= left; i--) { // [left, mid] must check the range
            l_sum += nums[i];
            max_l = std::max(max_l, l_sum);
        }
        int max_r = nums[mid + 1];
        int r_sum = 0;
        for (int i = mid + 1; i <= right; i++) { // [mid+1, right]
            r_sum += nums[i];
            max_r = std::max(max_r, r_sum);
        }
        
        /* compare three values */
        int lefthalf = maxarr(nums, left, mid);
        int righthalf = maxarr(nums, mid + 1, right);
        return std::max(max_l + max_r, std::max(lefthalf, righthalf));
    }
    
    int maxSubArray(vector<int>& nums) {
        return maxarr(nums, 0, nums.size() - 1);
    }
};