Maximum Subarray
問題簡介:
給定一個整數數組,因為數組中不同的且連續的子序列有不同的和,返回數組中子序列最大的和值
舉例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: [4,-1,2,1] 子序列有著最大的值 = 6.
解法一:
動態遞歸,一個記錄最終結果即最大值,一個記錄當前所求的和
複雜度分析:
時間複雜度:o(n)
空間複雜度:o(1)
小白刷題之路,請多指教— — 要麼大器晚成,要麼石沉大海。
2020-11-12 15:09:01 佚名
Maximum Subarray
問題簡介:
給定一個整數數組,因為數組中不同的且連續的子序列有不同的和,返回數組中子序列最大的和值
舉例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: [4,-1,2,1] 子序列有著最大的值 = 6.
解法一:
動態遞歸,一個記錄最終結果即最大值,一個記錄當前所求的和
複雜度分析:
時間複雜度:o(n)
空間複雜度:o(1)
小白刷題之路,請多指教— — 要麼大器晚成,要麼石沉大海。