leetcode/cpp/0053.cpp at master · xfmeng17/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
class Solution {
public:
  int maxSubArray(vector<int> &nums) {
    // return func1(nums);
    // return func2(nums);
    // return func3(nums);
    return func4(nums);
  }
  /*
   * basic dp
   * S(n, m) = Sum of nums[n] to nums[m]
   * Memory Limit Exceeded
   */
  int func1(vector<int> &nums) {
    int n = nums.size();
    if (n <= 0)
      return 0;

    int res = nums[0];
    vector<vector<int>> memo(n);
    for (int i = 0; i < n; i++) {
      memo[i].resize(n);
      for (int j = 0; j < n; j++) {
        if (i == j) {
          memo[i][j] = nums[i];
        } else {
          memo[i][j] = memo[i][j - 1] + nums[j];
        }
        res = max(res, memo[i][j]);
      }
    }

    return res;
  }
  // ** trim space dp, O(n^2) time
  int func2(vector<int> &nums) {
    if (nums.size() <= 0)
      return 0;

    int n = nums.size();
    int res = nums[0];
    for (int i = 0; i < n; i++) {
      int acc = 0;
      for (int j = i; j < n; j++) {
        acc += nums[j];
        res = max(res, acc);
      }
    }

    return res;
  }

  // ** O(n) time
  int func3(vector<int> &nums) {
    int res = nums[0];
    int pre = nums[0];
    for (int i = 1; i < nums.size(); i++) {
      cout << "pre = " << pre << endl;
      if (pre < 0) {
        pre = nums[i];
      } else {
        pre += nums[i];
      }
      res = max(res, pre);
    }
    return res;
  }

  // ** use hint, D&C
  int func4(vector<int> &nums) { return helper4(nums, 0, nums.size() - 1); }
  int helper4(vector<int> &nums, int lo, int hi) {
    if (lo > hi)
      return 0;
    if (lo == hi)
      return nums[lo];

    int mid = (lo + hi) / 2;
    int left = helper4(nums, lo, mid);
    int right = helper4(nums, mid + 1, hi);
    int cross = maxCrossingSum(nums, lo, hi, mid);

    return max(left, max(right, cross));
  }
  int maxCrossingSum(vector<int> &nums, int lo, int hi, int mid) {
    int sum = 0;
    int leftMax = nums[mid];
    for (int i = mid; i >= lo; i--) {
      sum += nums[i];
      leftMax = max(leftMax, sum);
    }
    sum = 0;
    int rightMax = nums[mid + 1];
    for (int i = mid + 1; i <= hi; i++) {
      sum += nums[i];
      rightMax = max(rightMax, sum);
    }
    return leftMax + rightMax;
  }

  // ** 2019-04-24 as-short-as-possible
  int func5(vector<int> &nums) {
    int pre = nums[0];
    int res = nums[0];
    for (int i = 1; i < nums.size(); i++) {
      if (pre < 0) {
        pre = nums[i];
      } else {
        pre += nums[i];
      }
      res = max(res, pre);
    }
    return res;
  }
};