leetcode_53 Maximum Subarray

y1chuan 發(fā)布于2019-08-15 13:37 / 1992人閱讀

摘要：如果單開元素加和更大判斷前面的子數(shù)組和是不是小于。此元素就成為了子數(shù)組的第一個元素。每次操作都要判斷，當(dāng)前是否是最大值，更新值。

題目詳情

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.

輸入：給定數(shù)組
輸出：找出給定數(shù)組所包含的連續(xù)的子數(shù)組中，元素加和最大的那一組，返回最大和

解法一

思路：

在遍歷數(shù)組的每一個元素的時候，我們都要思考一個問題——是從這個元素重新開啟一個子數(shù)組的加和更大，還是和前面的元素一起加和更大。

如果單開元素加和更大（判斷前面的子數(shù)組和是不是小于0）。我們就將保存當(dāng)前和的nowValue賦值為當(dāng)前元素。此元素就成為了子數(shù)組的第一個元素。

或者將當(dāng)前元素直接加入子數(shù)組。每次操作都要判斷，當(dāng)前value是否是最大值，更新max值。

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

        for(int i=0;i

GPU云服務(wù)器云服務(wù)器 leetcode_35_SearchIn subarray Maximum Leetcod

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68214.html

相關(guān)文章

leetcode53 Maximum Subarray 最大連續(xù)子數(shù)組

摘要：我們可以分別得出這三種情況下的最大子數(shù)列和，并比較得出最大的那個。我們只需要考慮左子列的最大和以及跨越了左右的中子列的最大值。題目要求 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 部分解答索引（持續(xù)更新～）

摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個索引嘻嘻。順序整理 1~50 1...

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

摘要：問題本質(zhì)本質(zhì)動態(tài)規(guī)劃問題。局部最優(yōu)，全局最優(yōu)。乘法問題，存在的情況是負(fù)數(shù)或者正數(shù)，或者從當(dāng)前數(shù)開始新的連續(xù)元素相乘可能發(fā)生的情況在某個節(jié)點，繼續(xù)之前的增大減小，從此節(jié)點轉(zhuǎn)折。所以只要在局部動態(tài)中，保持最大最小當(dāng)前，進行判斷保留即可。 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

摘要：復(fù)雜度思路要保留一個到某一位來看的最大值和最小值。因為在數(shù)組中有負(fù)數(shù)的出現(xiàn)，所以到這一位為止的能得到的最大值，可能是由之前的最大值和這個數(shù)相乘得到，也可能是最小值和這個數(shù)相乘得到的。 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