溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
【題目描述】
Given an array of integers, find a contiguous subarray which has the largest sum.
Notice:The subarray should contain at least one number.
給定一個整數數組，找到一個具有最大和的子數組，返回其最大和。
注意：子數組最少包含一個數
【題目鏈接】
http://www.lintcode.com/en/problem/maximum-subarray/
【題目解析】
O(n)就是一維DP.
假設A(0, i)區(qū)間存在k，使得[k, i]區(qū)間是以i結尾區(qū)間的最大值， 定義為Max[i], 在這里，當求取Max[i+1]時，
Max[i+1] = Max[i] + A[i+1], if (Max[i] + A[i+1] >0)
= 0, if(Max[i]+A[i+1] <0)，如果和小于零，A[i+1]必為負數，沒必要保留，舍棄掉
然后從左往右掃描，求取Max數字的最大值即為所求。
【參考答案】
http://www.jiuzhang.com/solutions/maximum-subarray/
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
