摘要:如果單開元素加和更大判斷前面的子數(shù)組和是不是小于。此元素就成為了子數(shù)組的第一個(gè)元素。每次操作都要判斷,當(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ù)組的每一個(gè)元素的時(shí)候,我們都要思考一個(gè)問(wèn)題——是從這個(gè)元素重新開啟一個(gè)子數(shù)組的加和更大,還是和前面的元素一起加和更大。
如果單開元素加和更大(判斷前面的子數(shù)組和是不是小于0)。我們就將保存當(dāng)前和的nowValue賦值為當(dāng)前元素。此元素就成為了子數(shù)組的第一個(gè)元素。
或者將當(dāng)前元素直接加入子數(shù)組。每次操作都要判斷,當(dāng)前value是否是最大值,更新max值。
int max = Integer.MIN_VALUE; int nowValue = 0; for(int i=0;i
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/68214.html
摘要:我們可以分別得出這三種情況下的最大子數(shù)列和,并比較得出最大的那個(gè)。我們只需要考慮左子列的最大和以及跨越了左右的中子列的最大值。 題目要求 Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given ...
摘要:前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來(lái)覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來(lái)覺得蠻亂的??赡艽蠹铱粗卜浅2环奖?。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...
摘要:?jiǎn)栴}本質(zhì)本質(zhì)動(dòng)態(tài)規(guī)劃問(wèn)題。局部最優(yōu),全局最優(yōu)。乘法問(wèn)題,存在的情況是負(fù)數(shù)或者正數(shù),或者從當(dāng)前數(shù)開始新的連續(xù)元素相乘可能發(fā)生的情況在某個(gè)節(jié)點(diǎn),繼續(xù)之前的增大減小,從此節(jié)點(diǎn)轉(zhuǎn)折。所以只要在局部動(dòng)態(tài)中,保持最大最小當(dāng)前,進(jìn)行判斷保留即可。 Given an integer array nums, find the contiguous subarray within an array (co...
摘要:復(fù)雜度思路要保留一個(gè)到某一位來(lái)看的最大值和最小值。因?yàn)樵跀?shù)組中有負(fù)數(shù)的出現(xiàn),所以到這一位為止的能得到的最大值,可能是由之前的最大值和這個(gè)數(shù)相乘得到,也可能是最小值和這個(gè)數(shù)相乘得到的。 Leetcode[152] Maximum Product Subarray Find the contiguous subarray within an array (containing at le...
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 ...
閱讀 2212·2021-09-30 09:47
閱讀 960·2021-08-27 13:01
閱讀 2959·2019-08-30 15:54
閱讀 3685·2019-08-30 15:53
閱讀 825·2019-08-29 14:07
閱讀 711·2019-08-28 18:16
閱讀 795·2019-08-26 18:37
閱讀 1406·2019-08-26 13:27