专栏首页Michael阿明学习之路程序员面试金典 - 面试题 16.17. 连续数列(DP/分治)

程序员面试金典 - 面试题 16.17. 连续数列(DP/分治)

1. 题目

给定一个整数数组(有正数有负数),找出总和最大的连续数列,并返回总和。

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

进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/contiguous-sequence-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

2.1 动态规划

  • dp[i] 表示包含第i位数字的最大和
  • 如果dp[i-1] > 0,则dp[i] = dp[i-1] + nums[i]
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
    	vector<int> dp(nums);
    	for(int i = 1; i < nums.size(); ++i)
    	{
    		if(dp[i-1] > 0)
    			dp[i] = max(dp[i], nums[i]+dp[i-1]);
    	}
    	return *max_element(dp.begin(),dp.end());
    }
};
  • 当前状态只与前面一个状态有关,可以压缩
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
    	int maxSum = nums[0], dp_i_1 = nums[0], dp_i;
    	for(int i = 1; i < nums.size(); ++i)
    	{
			dp_i = max(nums[i], nums[i]+dp_i_1);
			maxSum = max(maxSum, dp_i);
			dp_i_1 = dp_i;
    	}
    	return maxSum;
    }
};

2. 分治

  • 类似归并排序的思想
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
    	return divide(nums,0,nums.size()-1);
    }

    int divide(vector<int>& nums, int l, int r)
    {
    	if(l == r)
    		return nums[l];
    	int i, mid = l+((r-l)>>1);
    	int Lsum = divide(nums,l,mid);//分治
    	int Rsum = divide(nums,mid+1,r);
    	//合并
    	int Ls = 0, Rs = 0, maxL = INT_MIN, maxR = INT_MIN;
    	for(i = mid; i >= 0; --i)//必须从中间开始遍历,便于求跨在两侧的最大和
    	{
    		Ls += nums[i];//左侧的和
    		maxL = max(maxL, Ls);//最大的左侧和
    	}
    	for(i = mid+1; i <= r; ++i)
    	{
    		Rs += nums[i];//右侧和
    		maxR = max(maxR, Rs);//最大的右侧和
    	}
    	return max(maxL+maxR, max(Lsum,Rsum));
    	//        最大的左+右和,最大的左侧和,最大的右侧和
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1262. 可被三整除的最大和(DP)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/greatest-sum-divisible-by-t...

    Michael阿明
  • LeetCode 368. 最大整除子集(DP)

    给出一个由无重复的正整数组成的集合,找出其中最大的整除子集,子集中任意一对 (Si,Sj) 都要满足:Si % Sj = 0 或 Sj % Si = 0。

    Michael阿明
  • LeetCode 1498. 满足条件的子序列数目(排序+二分查找+快速幂)

    请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。

    Michael阿明
  • 力扣416——分割等和子集

    这道题主要涉及的是动态规划,类似背包问题,主要还是需要找出状态转移方程,优化时可以考虑采用深度优先搜索。

    健程之道
  • 漫画:动态规划系列 第二讲

    在上一篇文章中,我们讲解了DP的概念并且通过示例了解了什么是动态规划。本篇中,我们将继续通过1道简单题型,进一步学习动态规划的思想。

    程序员小浩
  • 算法细节系列(21):贪心有理?

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 初级算法-动态规划

    动态规划主要是解一些递归问题,也就是将递归写成非递归方式,因为编辑器无法正确对待递归,递归方法会导致很多计算结果被重复计算,比如菲波那切数列。

    方丈的寺院
  • 动态规划设计

    输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

    用户7625070
  • 详解三道一维的动态规划算法题

    在一条直线上,有n个房屋,每个房屋中有数量不等的财宝,有一个盗 贼希望从房屋中盗取财宝,由于房屋中有报警器,如果同时从相邻的两个房屋中盗取财宝就会触发报警器。问...

    帅地
  • 【leetcode刷题】T165-最长上升子序列

    https://leetcode-cn.com/problems/longest-increasing-subsequence/

    木又AI帮

扫码关注云+社区

领取腾讯云代金券