OJ lintcode 最小子數(shù)組

給定一個整數(shù)數(shù)組坊萝,找到一個具有最小和的子數(shù)組。返回其最小和许起。
注意事項
子數(shù)組最少包含一個數(shù)字
您在真實的面試中是否遇到過這個題十偶?
Yes
樣例
給出數(shù)組[1, -1, -2, 1],返回 -3

class Solution {
public:
    /**
     * @param nums: a list of integers
     * @return: A integer denote the sum of minimum subarray
     */
    int minSubArray(vector<int> nums) {
        // write your code here
        int sum=0;  //記錄當前最小的結(jié)果
        int min=0;  //記錄最小的結(jié)果
        int p_min=nums[0];
        int flag=0;

        for(int i=0;i<nums.size();i++){
            sum=sum+nums[i];
            if(sum>0){
                sum=0;
            }
            else{
                if(min>sum){
                    min=sum;
                }
            }

            //記錄數(shù)組中的最小的元素
            if(p_min>nums[i]){
                p_min=nums[i];
            }
            if(nums[i]<0){
                flag=-1; //如果flag==-1 园细,也就是說明其中有一個元素是負數(shù)
            }
        }

        if(flag==-1){
            return min;  //這是存在有負數(shù)的情況
        }
        else{
            return p_min;  //這是所有元素都為整數(shù)的情況
        }
        //return min< p_min ? min:p_min;

    }
};

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末惦积,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子猛频,更是在濱河造成了極大的恐慌狮崩,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,084評論 6 503
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件鹿寻,死亡現(xiàn)場離奇詭異睦柴,居然都是意外死亡,警方通過查閱死者的電腦和手機毡熏,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,623評論 3 392
  • 文/潘曉璐 我一進店門坦敌,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人,你說我怎么就攤上這事狱窘《潘常” “怎么了?”我有些...
    開封第一講書人閱讀 163,450評論 0 353
  • 文/不壞的土叔 我叫張陵蘸炸,是天一觀的道長躬络。 經(jīng)常有香客問我,道長搭儒,這世上最難降的妖魔是什么穷当? 我笑而不...
    開封第一講書人閱讀 58,322評論 1 293
  • 正文 為了忘掉前任,我火速辦了婚禮仗嗦,結(jié)果婚禮上膘滨,老公的妹妹穿的比我還像新娘。我一直安慰自己稀拐,他們只是感情好火邓,可當我...
    茶點故事閱讀 67,370評論 6 390
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著德撬,像睡著了一般铲咨。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上蜓洪,一...
    開封第一講書人閱讀 51,274評論 1 300
  • 那天纤勒,我揣著相機與錄音,去河邊找鬼隆檀。 笑死摇天,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的恐仑。 我是一名探鬼主播泉坐,決...
    沈念sama閱讀 40,126評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼裳仆!你這毒婦竟也來了腕让?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 38,980評論 0 275
  • 序言:老撾萬榮一對情侶失蹤歧斟,失蹤者是張志新(化名)和其女友劉穎纯丸,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體静袖,經(jīng)...
    沈念sama閱讀 45,414評論 1 313
  • 正文 獨居荒郊野嶺守林人離奇死亡觉鼻,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,599評論 3 334
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了勾徽。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片滑凉。...
    茶點故事閱讀 39,773評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡统扳,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出畅姊,到底是詐尸還是另有隱情咒钟,我是刑警寧澤,帶...
    沈念sama閱讀 35,470評論 5 344
  • 正文 年R本政府宣布若未,位于F島的核電站朱嘴,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏粗合。R本人自食惡果不足惜萍嬉,卻給世界環(huán)境...
    茶點故事閱讀 41,080評論 3 327
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望隙疚。 院中可真熱鬧壤追,春花似錦、人聲如沸供屉。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,713評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽伶丐。三九已至悼做,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間哗魂,已是汗流浹背肛走。 一陣腳步聲響...
    開封第一講書人閱讀 32,852評論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留录别,地道東北人朽色。 一個月前我還...
    沈念sama閱讀 47,865評論 2 370
  • 正文 我出身青樓,卻偏偏與公主長得像组题,于是被迫代替她去往敵國和親纵搁。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 44,689評論 2 354

推薦閱讀更多精彩內(nèi)容

  • 給定一個整數(shù)數(shù)組往踢,找到一個具有最大和的子數(shù)組,返回其最大和徘层。注意事項子數(shù)組最少包含一個數(shù)您在真實的面試中是否遇到過...
    DayDayUpppppp閱讀 416評論 0 0
  • 題目 給定一個整數(shù)數(shù)組峻呕,找到一個具有最小和的子數(shù)組。返回其最小和趣效。 ** 注意事項子數(shù)組最少包含一個數(shù)字 ** 樣...
    六尺帳篷閱讀 1,546評論 0 1
  • 題目前的數(shù)字是對應(yīng)的lintcode的題目序號 14.二分查找 給定一個排序的整數(shù)數(shù)組(升序)和一個要查找的整數(shù)t...
    mytac閱讀 675評論 1 2
  • 3.10 69.給出一棵二叉樹瘦癌,返回其節(jié)點值的層次遍歷(逐層從左往右訪問) 二叉樹的層次遍歷樣例給一棵二叉樹 {3...
    mytac閱讀 1,076評論 3 3
  • *面試心聲:其實這些題本人都沒怎么背,但是在上海 兩周半 面了大約10家 收到差不多3個offer,總結(jié)起來就是把...
    Dove_iOS閱讀 27,139評論 30 470