解题思路

【leetcode题解】最大子数和 - 图1

代码

  1. // class Solution {
  2. // public:
  4. //     int crossSum(vector<int> & nums, int left, int right, int p)
  5. //     {
  6. //         if(left == right) return nums[left];
  7. //         int currSum = 0, leftSum = INT_MIN, rightSum = INT_MIN;
  10. //         for(int i = p ; i > left-1 ; i--)
  11. //         {
  12. //             currSum += nums[i];
  13. //             leftSum = max(currSum, leftSum);
  14. //         }
  16. //         currSum = 0;
  17. //         for(int i = p + 1 ; i < right + 1 ; i++)
  18. //         {
  19. //             currSum += nums[i];
  20. //             rightSum = max(currSum, rightSum);
  21. //         }
  23. //         return leftSum + rightSum;
  24. //     }
  27. //     int unitSum(vector<int> & nums, int left, int right)
  28. //     {
  29. //         if(left == right)
  30. //         {
  31. //             return nums[left];
  32. //         }
  34. //         int leftSum;
  35. //         int rightSum;
  36. //         int RcrossSum;
  38. //         leftSum = unitSum(nums, left, (left+right)/2);
  39. //         rightSum = unitSum(nums, (left+right)/2+1, right);
  40. //         RcrossSum = crossSum(nums, left, right, (left+right)/2);
  42. //         return max(leftSum, max(rightSum, RcrossSum));
  43. //     }
  46. //     int maxSubArray(vector<int>& nums) {
  47. //         return unitSum(nums, 0, nums.size()-1);
  48. //     }
  49. // };
  51. class Solution {
  52. public:
  55.     int maxSubArray(vector<int>& nums) {
  56.         int currMax = nums[0];
  57.         int reMax = nums[0];
  59.         for(int i = 1 ; i < nums.size() ; i++)
  60.         {
  61.             currMax = max(nums[i], currMax + nums[i]);
  62.             reMax = max(currMax, reMax);
  63.         }
  65.         return reMax;
  66.     }
  67. };