День 61: Максимальный подмассив

LeetCode 53. Максимальный подмассив

Sol динамического программирования: O (n)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_so_far = INT_MIN, max_tmp = 0;
        
        for (int elem : nums) {
            max_tmp += elem;
            max_so_far = max(max_tmp, max_so_far);
            if (max_tmp < 0) {
                max_tmp = 0;
            }            
        }
        return max_so_far;
    }
};

Разделяй и властвуй Соль: O(n)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return divide_and_conquer(nums, 0, nums.size() - 1);
    }
    
    int divide_and_conquer(vector<int>& nums, int left, int right) {
        if (left > right) {
            return INT_MIN;
        }
        
        int mid = left + (right - left) / 2, max_left_tmp = 0, max_right_tmp = 0;
        
        int left_max = divide_and_conquer(nums, left, mid - 1);
        int right_max = divide_and_conquer(nums, mid + 1, right);
        
        for (int i = mid - 1, sum = 0; i >= left; i--) {
            sum += nums[i];
            max_left_tmp = max(max_left_tmp, sum);
        }
        
        for (int i = mid + 1, sum = 0; i <= right; i++) {
            sum += nums[i];
            max_right_tmp = max(max_right_tmp, sum);
        }
        
        return max(max(left_max, right_max), max_left_tmp + max_right_tmp + nums[mid]);
    }
};