力扣算法题—053最大子序之和

 1 #include "000库函数.h"
 2 
 3 //一想到又是遍历
 4 class Solution {
 5 public:
 6     int maxSubArray(vector<int>& nums) {
 7         int res=nums[0];
 8         for (int i = 0; i < nums.size(); ++i) {
 9             int sum = nums[i];
10             res = res > sum ? res : sum;
11             for (int j = i + 1; j < nums.size(); ++j) {
12                 sum += nums[j];
13                 res = res > sum ? res : sum;
14             }
15         }
16         return res;
17     }
18 };
19 
20 //使用滑窗来做
21 class Solution {
22 public:
23     int maxSubArray(vector<int>& nums) {
24         int res = nums[0];
25         int sum = -1;
26         for (auto a : nums) {
27             sum = max(a, sum + a);
28             res = max(res, sum);
29         }
30         return res;
31     }
32 };
33 
34 
35 
36 //用分治法来计算，将数组一分为二，从中间来开始遍历
37 
38 class Solution {
39 public:
40     int maxSubArray(vector<int>& nums) {
41         return helper(nums, 0, nums.size() - 1);
42     }
43     int helper(vector<int>nums, int left, int right) {
44         if (left >= right)return nums[left];
45         int mid = (left + right) / 2;
46         int lmax = helper(nums, left, mid - 1);//左移
47         int rmax = helper(nums, mid + 1, right);//右移
48         int mmax = nums[mid], t = mmax;
49         for (int i = mid - 1; i >= left; --i) {//左移计算
50             t += nums[i];
51             mmax = mmax > t ? mmax : t;
52         }
53         t = mmax;
54         for (int i = mid + 1; i <= right; ++i) {
55             t += nums[i];
56             mmax = mmax > t ? mmax : t;
57         }
58         return mmax > (rmax > lmax ? rmax : lmax) ? mmax : (rmax > lmax ? rmax : lmax);
59     }
60 };
61 
62 void T053() {
63     Solution s;
64     vector<int>v;
65     v = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
66     cout << s.maxSubArray(v) << endl;
67 }