题目:
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-subarray
动态规划解法的思路:
- 假定第一个元素为最终返回的子序和,设为result
- 设定数组元素相加和为 sum
- 遍历数组,将元素相加获得的sum与result对比,取最大
- 时间复杂度 O(n)
代码:
class MaxSubArray { function solution($nums) { $result = $nums[0]; $sum = 0; for ($i=1; $i < count($nums); $i++) { if ($sum > 0) { $sum += $nums[$i]; } else { $sum = $nums[$i]; } $result = max($result, $sum); } return $result; } }
Visits: 514