成都做网站公司,东莞市网站建设怎么样,莱州网站建设报价,长春网站建设模板文章目录1. 题目描述2. 解题2.1 暴力求解2.2 动态规划1. 题目描述
题目链接#xff1a;https://leetcode-cn.com/problems/maximum-subarray/ 《剑指Offer》同题#xff1a;面试题42. 连续子数组的最大和
给定一个整数数组 nums #xff0c;找到一个具有最大和的连续子数组…
文章目录1. 题目描述2. 解题2.1 暴力求解2.2 动态规划1. 题目描述
题目链接https://leetcode-cn.com/problems/maximum-subarray/ 《剑指Offer》同题面试题42. 连续子数组的最大和
给定一个整数数组 nums 找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大为 6。进阶: 如果你已经实现复杂度为 O(n) 的解法尝试使用更为精妙的分治法求解。 2. 解题
类似题目程序员面试金典 - 面试题 17.24. 最大子矩阵转成一维最大子序和 DP
2.1 暴力求解
双重循环On2时间复杂度
class Solution {
public:int maxSubArray(vectorint nums) {if(nums.size() 0) return 0;int max nums[0];//最大值int sum0, i, j;for(i 0; i nums.size(); i){sum0;for(j i; j nums.size(); j){sum nums[j];if(sum max) //实时更新最大值max sum;}}return max;}
};2.2 动态规划
状态转移方程 maxsum[i]max(maxsum[i−1]num[i],num[i])maxsum[i] max( maxsum[i-1] num[i], num[i] )maxsum[i]max(maxsum[i−1]num[i],num[i]) 表示到i元素最大子序列和的最大值 把所有maxsum[i]的元素最大值返回就是答案
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]}时间复杂度On i012345678nums[i]-21-34-121-54maxsum[i]-2max(-21,1)1max(1-3,-3) -2435615
class Solution
{
public:int maxSubArray(vectorint nums){int maxSumOfArr INT_MIN, maxsum 0;for(int i 0; i nums.size(); i){maxsum max(nums[i],maxsumnums[i]);maxSumOfArr max(maxSumOfArr, maxsum);}return maxSumOfArr;}
};class Solution {
public:int maxSubArray(vectorint nums) {int i, n nums.size(), ans nums[0];vectorint 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];elsedp[i] nums[i];ans max(ans,dp[i]);}return ans;}
};
