题目

leetcode-53. Maximum Subarray

类似:

leetcode-152. Maximum Product Subarray

要点是记录当前最大值,与最小值。

计算当前最值有三种可能:

  1. 当前值
  2. 前一个最大值与当前值之积
  3. 前一个最小值与当前值之积

从这三种取出最小值和最大值。 (从三个可能优化到两个)

leetcode-325. Maximum Size Subarray Sum Equals k

leetcode-643. Maximum Average Subarray I

leetcode-644. Maximum Average Subarray II

leetcode-918. Maximum Sum Circular Subarray

689. Maximum Sum of 3 Non-Overlapping Subarrays

分析

这是一维数组求最大子数组之和的问题。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_sum  = INT_MIN; 
        int max_pre  = 0; 
        int max_cur = 0; 
        
         for (int i = 0; i  < nums.size(); i++){
             int cur_item = nums[i]; 
             if(max_pre  > 0 ){
                 max_cur = max_pre + cur_item;
             }else {
                 max_cur  = cur_item; 
             }
             
             max_sum = max(max_sum, max_cur);
             max_pre = max_cur; 
         }
        
        return  max_sum; 
    }
};
 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
#include <iostream>
using namespace std;


int max_subarr_sum(int arr[], int n)
{
    // 最大值
    int max_sum = INT_MIN;

    // 前一个位置最大值 
    int max_pre = 0;
    
    // 当前位置最大值 
    int max_cur = 0;
    
    // 遍历
    for (int i = 0; i < n; i++)
    {
        int cur_item  = arr[i];
        if (max_pre > 0) {
            max_cur = max_pre + cur_item;
        } else {
            max_cur = cur_item; 
        }

        max_sum  = max(max_sum, max_cur);
        max_pre = max_cur;

    }

    return max_sum;
}

int main()
{
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "The sum of contiguous sub-array with the largest sum is " <<
            max_subarr_sum(arr, n);

    return 0;
}

运行测试

欢迎关注

欢迎关注微信公众帐号:沉风网事(savewind)

沉风网事