[LeetCode] Maximum Subarray Sum

Dynamic Programming

There is a nice introduction to the DP algorithm in this Wikipedia article. The idea is to maintain a running maximum smax and a current summation sum. When we visit each num in nums, addnum to sum, then update smax if necessary or reset sum to 0 if it becomes negative.

The code is as follows.

 class Solution {

 public:

     int maxSubArray(vector<int>& nums) {

         int sum = , smax = INT_MIN;

         for (int num : nums) {

             sum += num;

             if (sum > smax) smax = sum;

             if (sum < ) sum = ;

         }

         return smax;

     }

 };

Divide and Conquer

The DC algorithm breaks nums into two halves and find the maximum subarray sum in them recursively. Well, the most tricky part is to handle the case that the maximum subarray may span the two halves. For this case, we use a linear algorithm: starting from the middle element and move to both ends (left and right ends), record the maximum sum we have seen. In this case, the maximum sum is finally equal to the middle element plus the maximum sum of moving leftwards and the maximum sum of moving rightwards.

Well, the code is just a translation of the above idea.

 class Solution {

 public:

     int maxSubArray(vector<int>& nums) {

         int smax = INT_MIN, n = nums.size();

         return maxSub(nums, , n - , smax);

     }

 private:

     int maxSub(vector<int>& nums, int l, int r, int smax) {

         if (l > r) return INT_MIN;

         int m = l + ((r - l) >> );

         int lm = maxSub(nums, l, m - , smax); // left half

         int rm = maxSub(nums, m + , r, smax); // right half

         int i, sum, ml = , mr = ;

         // Move leftwards

         for (i = m - , sum = ; i >= l; i--) {

             sum += nums[i];

             ml = max(sum, ml);

         }

         // Move rightwards

         for (i = m + , sum = ; i <= r; i++) {

             sum += nums[i];

             mr = max(sum, mr);

         }

         return max(smax, max(ml + mr + nums[m], max(lm, rm)));

     }

 };

巴特西

[LeetCode] Maximum Subarray Sum

最新文章

热门文章