LeetCode刷算法题 - 53. Maximum Subarray

写在前面:

程序员分两种，会算法的程序员和不会算法的程序员。几乎没有一个一线互联网公司招聘任何类别的技术人员是不考算法的，程序猿们都懂的，现在最权威流行的刷题平台就是 LeetCode。

LeetCode原题链接

string - C++ Reference

C++中int与string的相互转换

C++ Map常见用法说明

Question:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution

五大常用算法：分治、动态规划、贪心、回溯和分支界定

以下代码皆是本人用 C++写的，觉得还不错的话别忘了点个赞哦。各位同学们如果有其他更高效解题思路还请不吝赐教，多多学习。

A1、暴力解法

粗暴进行循环遍历，问题复杂化，不可取
算法时间复杂度 O(n^2)Time Limit Exceeded，代码如下

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() <= 0) return 0;
        
        int sumMax = 0;
        // 1，2，i……个数为子数组的和进行比较
        for (int i=0; i<nums.size(); i++) {
            int sumsub = 0;
            // i个数子数组的最大和
            for (int j=0; j<nums.size()-i; j++) {
                // nums[j]开始i个数的和
                int sumi = 0;
                for (int k=0; k<=i; k++) {
                    sumi += nums[j+k];
                }
                sumsub = sumsub<sumi || j==0 ? sumi :sumsub;
            }
            sumMax = sumMax<sumsub || i==0 ? sumsub : sumMax;
        }
        return sumMax;
    }
};

A2、一般解法

一层循环
算法时间复杂度 O(n)，Runtime: 8 ms，代码如下

int x=[](){
   std::ios::sync_with_stdio(false);  //关闭STDIN和CIN同步 减少CIN读入的时间，可以减少50%以上。
    cin.tie(NULL);
    return 0;
}();

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
   if (nums.size()==0) return 0;
    
    int sumMax = nums[0];
    int sum = 0;
    for (int i=0; i<nums.size(); i++) {
        sum += nums[i];
        if (sum>sumMax) {
            sumMax = sum;
        }
        if (sum<0) {
            sum = 0;
        }
    }
    return sumMax;
    }
};

A3、分治策略 Divide-and-Conquer(P)

五大常用算法：分治、动态规划、贪心、回溯和分支界定

• 一层循环，分治策略。
• 现在是计算n 个数字数组的最大子数组和，可以 分解为 n 个子问题
• 即从0计数以 nums[i-1]为结尾的前 i 个数的子数组的最大和，则需循环计算 出 n 个最大和，其中最大的即为整个数组的最大子数组和。
  算法时间复杂度 O(n)，Runtime: 7 ms，代码如下

int x=[](){
    std::ios::sync_with_stdio(false);  //关闭STDIN和CIN同步 减少CIN读入的时间，可以减少50%以上。
    cin.tie(NULL);
    return 0;
}();

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size()==0) return 0;
        
        int dpi = 0;
        int sumMax = INT32_MIN;
        for (int i=0; i<nums.size(); i++) {
            if (dpi<0) {
                dpi = nums[i];
            } else{
                dpi = nums[i] + dpi;
            }
            sumMax = std:: max(dpi, sumMax);
        }
        return sumMax;
    }
};

引用相关

LeetCode 官网