leetcode_53 Maximum Subarray

y1chuan 发布于2019-08-15 13:37 / 1968人阅读

摘要：如果单开元素加和更大判断前面的子数组和是不是小于。此元素就成为了子数组的第一个元素。每次操作都要判断，当前是否是最大值，更新值。

题目详情

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

输入：给定数组
输出：找出给定数组所包含的连续的子数组中，元素加和最大的那一组，返回最大和

解法一

思路：

在遍历数组的每一个元素的时候，我们都要思考一个问题——是从这个元素重新开启一个子数组的加和更大，还是和前面的元素一起加和更大。

如果单开元素加和更大（判断前面的子数组和是不是小于0）。我们就将保存当前和的nowValue赋值为当前元素。此元素就成为了子数组的第一个元素。

或者将当前元素直接加入子数组。每次操作都要判断，当前value是否是最大值，更新max值。

        int max = Integer.MIN_VALUE;
        int nowValue = 0;

        for(int i=0;i

云服务器 GPU云服务器 leetcode_35_SearchIn subarray Maximum Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68214.html

leetcode53 Maximum Subarray 最大连续子数组

摘要：我们可以分别得出这三种情况下的最大子数列和，并比较得出最大的那个。我们只需要考虑左子列的最大和以及跨越了左右的中子列的最大值。题目要求 Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given ...

Bamboy 2019-08-14 18:08 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
leetcode-152-Maximum Product Subarray

摘要：问题本质本质动态规划问题。局部最优，全局最优。乘法问题，存在的情况是负数或者正数，或者从当前数开始新的连续元素相乘可能发生的情况在某个节点，继续之前的增大减小，从此节点转折。所以只要在局部动态中，保持最大最小当前，进行判断保留即可。 Given an integer array nums, find the contiguous subarray within an array (co...

thursday 2019-07-30 17:32 评论0 收藏0
Leetcode[152] Maximum Product Subarray

摘要：复杂度思路要保留一个到某一位来看的最大值和最小值。因为在数组中有负数的出现，所以到这一位为止的能得到的最大值，可能是由之前的最大值和这个数相乘得到，也可能是最小值和这个数相乘得到的。 Leetcode[152] Maximum Product Subarray Find the contiguous subarray within an array (containing at le...

_ipo 2019-08-14 16:49 评论0 收藏0
[LeetCode] Maximum Size Subarray Sum Equals k

Problem Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isnt one, return 0 instead. Note The sum of the entire nums array is guaranteed to fit ...

MudOnTire 2019-08-15 15:47 评论0 收藏0