題目描述
輸入一個整型陣列，數組裡有正數也有負數。陣列中的一個或連續多個整陣列成一個子陣列。求所有子陣列的和的最大值。要求時間複雜度為 O（n）。
示例
輸入 ［1，-2，3，10，-4，7，2，-5］輸出 18說明 輸入的陣列為{1，-2，3，10，—4，7，2，一5}，和最大的子陣列為{3，10，一4，7，2}，因此輸出為該子陣列的和 18。
/**歡迎關注微信公眾號：Java的學習之路資料非常全，java初級到高階都有，影片，電子書，面試寶典，簡歷模板，經典案例，原始碼分析。目錄 http：//mp。weixin。qq。com/mp/homepage？__biz=MzUzMjA2NDU2OQ==&hid=19&sn=c193d89a0fb5d4c67c8c9d399712ca62&scene=18%23wechat_redirect框架 http：//mp。weixin。qq。com/mp/homepage？__biz=MzUzMjA2NDU2OQ==&hid=3&sn=e693a1ac2f05398a9bc0adcdbc5d28a9&scene=18%23wechat_redirect影片及開發工具 http：//mp。weixin。qq。com/mp/homepage？__biz=MzUzMjA2NDU2OQ==&hid=4&sn=6245b5f07da976ba7df67ba39a9fa8d1&scene=18#wechat_redirect面試技巧及簡歷 http：//mp。weixin。qq。com/mp/homepage？__biz=MzUzMjA2NDU2OQ==&hid=7&sn=674252f32c8585f9e62b5b87335e5a83&scene=18#wechat_redirect */
思路分析
注意需要這個題目的問題，第一個連續子陣列是一個或者連續多個整陣列成的。第二個這個題目是要求我們求和，沒有讓我們將最大和的子陣列打印出來。
1、從陣列的開頭向下走，sum來記錄連續的和，max來記錄最大的值，sum值為0，max為第一個值，陣列不斷的往下走，不斷的來累積更新max的值。如果當sum /* * 時間複雜度：O（n） * 空間複雜度：O（1） */ public int FindGreatestSumOfSubArray2（int［］ array） { int max = array［0］； int sum = 0； for （int i = 0； i < array。length； i++） { sum += array［i］； if （sum > max） { max = sum； } if （sum < array［0］） { sum = 0； } } return max； } 2、動態規劃 因為從題目來看，這是一個典型的動態規劃的題目。動態規劃演算法的核心 就是記住已經解決過的子問題的解 。對於我們這個題目就是這樣的。因此解法如下： /* * 時間複雜度：O（n） * 空間複雜度：O（n） */ public static int FindGreatestSumOfSubArray（int［］ array） { int max = array［0］； for （int i = 1； i < array。length； i++） { array［i］ += array［i - 1］ > 0 ？ array［i - 1］ ： 0； max = Math。max（max， array［i］）； } return max； }
