本文共 1948 字，大约阅读时间需要 6 分钟。

1. 题目描述

题目链接：https://leetcode-cn.com/problems/maximum-subarray/

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

2. 解题

类似题目：

2.1 暴力求解

双重循环O（n²）时间复杂度

class Solution {
   public:    int maxSubArray(vector
   
    & nums)     {
           if(nums.size() == 0)             return 0;        int max = nums[0];//最大值        int sum=0, i, j;        for(i = 0; i< nums.size(); ++i)        {
               sum=0;            for(j = i; j< nums.size(); ++j)            {
                   sum += nums[j];                if(sum > max) //实时更新最大值                    max = sum;            }        }        return max;    }};
   

2.2 动态规划

状态转移方程

if maxsum[i-1] + num[i] >= num[i]	//num[i]起	maxsum[i] = maxsum[i-1] + num[i]else 	maxsum[i] = num[i]maxSumOfSubArr = max{maxsum[0],maxsum[i]...maxsum[n-1]}

时间复杂度O（n）

class Solution{
   public:    int maxSubArray(vector
   
    & nums)    {
           int maxSumOfArr = INT_MIN, maxsum = 0;        for(int i = 0; i < nums.size(); ++i)        {
               maxsum = max(nums[i],maxsum+nums[i]);            maxSumOfArr = max(maxSumOfArr, maxsum);        }        return maxSumOfArr;    }};
   

class Solution {
   public:    int maxSubArray(vector
   
    & nums) {
           int i, n = nums.size(), ans = nums[0];        vector
    
      dp(n,0);        dp[0] = nums[0];        for(i = 1; i < n; ++i)        {
           	if(dp[i-1] >= 0)        		dp[i] = nums[i]+dp[i-1];        	else        		dp[i] = nums[i];        	ans = max(ans,dp[i]);        }        return ans;    }};
    
   

转载地址：http://zqetf.baihongyu.com/