【leetcode刷题】T15-最大子数组和
今天分享leetcode第15篇文章，也是leetcode第53题—最大子数组和（Maximum Subarray）
【英文题目】（学习英语的同时，更能理解题意哟~）
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.【中文题目】
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。【思路】
这道题可以暴力破解，即得到每个连续子数组并求和，返回最大值，但是时间复杂度特别高。
其实可以使用动态规划（如果不明白可以暂时忽略这个概念），我们记录到第i个元素的最大连续子数组和为dp[i]，那么当前的最大连续子数组和dp[i]，要么是自己的值nums[i]，要么是到前一个元素为止的最大连续子数组和+自己的值（dp[i-1] + nums[i]）。
因此可以得到以下两个公式：
1）dp[i] = nums[0], i=0时
2）dp[i] =max(0, dp[i-1]) + nums[i] , i>0时
查找dp数组中的最大值并返回即可。
由于dp[i]用完以后没有作用，所以可以使用变量来代替数组，节省空间。
【代码】
python版本
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 1:
return None
res = nums[0]
dp = nums[0]
for num in nums[1:]:
# dp[n] = max(dp[n-1] + nums[n], nums[n])
dp = max(dp + num, num)
if dp > res:
res = dp
return resC++版本
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.size() < 1)
return NULL;
int res = nums[0];
int dp = nums[0];
for(int i=1; i < nums.size(); i++){
// dp[n] = max(dp[n-1] + nums[n], nums[n])
if(dp < 0)
dp = nums[i];
else
dp += nums[i];
if(dp > res)
res = dp;
}
return res;
}
};思考：如果需要返回该子数组的首尾下标，应该怎么处理呢？
本文参与?腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-03-11，如有侵权请联系?cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读