Cpp divide and conquer solution


  • 0
    W
    struct Data {
      int left;
      int mid;
      int right;
      Data(int l, int m, int r): left(l), mid(m), right(r) {}
    };
    
    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            dnc(nums, 0, nums.size() - 1);
            return sum;
        }
        
        Data dnc(const vector<int>& nums, int l, int r) {
            if (l < r) {
                int m = l + (r - l) / 2;
                auto left = dnc(nums, l, m);
                auto right = dnc(nums, m + 1, r);
                sum = max(sum, max(left.right, left.mid) + max(right.left, right.mid));
                return Data(
                    max(left.left, right.left + left.mid), // left value
                    left.mid + right.mid, // mid value
                    max(right.right, left.right + right.mid) // right value
                );
            }
            sum = max(sum, nums[l]);
            return Data(nums[l], nums[l], nums[l]);
            
        }
    private:
        int sum{numeric_limits<int>::min()};
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.