leetcode/algorithms/cpp/053.maximum_subarray/maximum_subarray.cc at main · leschus/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// Source: https://leetcode-cn.com/problems/maximum-subarray
// Author: Shihao Liu
// Date: 2021-11-24

#include <climits>
#include <vector>
#include <iostream>
using namespace std;

// 超出时间限制
class Solution_1 {
 public:
  /**
  * @brief 暴力求解
  *
  * 时间复杂度: O(n^2)
  */
  int maxSubArray(vector<int>& nums) {
    int max = INT_MIN, tmp;
    for (int i = 0; i < nums.size(); i++) {
      tmp = 0;
      for (int j = i; j < nums.size(); j++) {
        tmp += nums[j];
        if (tmp > max) {
          max = tmp;
        }
      }
    }
    return max;
  }

};

// AC
class Solution_2 {
 private:
  int maxSub(vector<int> &nums, int left, int right) {
    if (left == right) {
      return nums[left];
    }
    int mid = (left + right) / 2;
    int lmax = maxSub(nums, left, mid);
    int rmax = maxSub(nums, mid + 1, right);
    int cross_lmax = nums[mid], cross_rmax = nums[mid + 1], cross_max;
    int tmp = nums[mid], i;
    for (i = mid - 1; i >= left; i--) {
      tmp += nums[i];
      if (tmp > cross_lmax) {
        cross_lmax = tmp;
      }
    }
    tmp = nums[mid + 1];
    for (i = mid + 2; i <= right; i++) {
      tmp += nums[i];
      if (tmp > cross_rmax) {
        cross_rmax = tmp;
      }
    }
    cross_max = cross_lmax + cross_rmax;
    // 比较得到三种情形下的最大值
    if (lmax > rmax) {
      if (lmax > cross_max) {
        return lmax;
      } else {
        return cross_max;
      }
    } else {
      if (rmax > cross_max) {
        return rmax;
      } else {
        return cross_max;
      }
    }
  }
 public:
  /**
  * @brief 分治法, 递归(参考算法导论4.1)
  *
  * 时间复杂度: O(nlogn)
  *
  * 分治策略: 取数组A[low...high]的中间位置mid. 最大子数组可能存在于:
  *   * 左半数组A[low, mid]中;
  *   * 右半数组A[mid+1, high]中;
  *   * 跨越了mid元素的子数组A[i...j]中, 其中low <= i <= mid < j <= high;
  *
  * 算法导论上的策略可以用来输出最大子数组的具体位置不仅仅是其最大和, 用在这个
  * 题目上有点大材小用了, 所以虽然AC, 但并不理想.
  */
  int maxSubArray(vector<int>& nums) {
    return maxSub(nums, 0, nums.size() - 1);
  }

};

class Solution_3 {
 public:
  /**
  * @brief 动态规划
  *
  * 时间复杂度:
  *
  * 记f(i)为以i结尾的最大子序列和, 则:
  *     f(i) = max{f(i-1) + nums[i], nums[i]}
  * 遍历一遍数组即可求得每一个f(i), 这里不需要用数组保存每一个f(i), 根据公式,
  * 只需要再进行第i轮时用到上一轮求得的f(i)即可
  * 数组f中的最大值即为所求.
  *
  */
  int maxSubArray(vector<int>& nums) {
    int max, pre;
    max = pre = nums[0];
    for (int i = 1; i < nums.size(); i++) {
      if (pre + nums[i] >= nums[i]) {
        pre += nums[i];
      } else {
        pre = nums[i];
      }
      if (pre > max) {
        max = pre;
      }
    }
    return max;
  }

};


int main() {
  vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
  Solution_1 sol1;
  cout << sol1.maxSubArray(nums) << endl;
  Solution_2 sol2;
  cout << sol2.maxSubArray(nums) << endl;

  Solution_3 sol3;
  cout << sol3.maxSubArray(nums) << endl;
}