goden1617

面试题 16.17.连续数列

1. 题目描述

给定一个整数数组，找出总和最大的连续数列，并返回总和。

示例：

输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶： 如果你已经实现复杂度为 O( n ) 的解法，尝试使用更为精妙的分治法求解。

标签 数组 分治 动态规划

2. 解题

1. 动态规划 dp[i] = max{array[i], array[i]+dp[i-1]}

2. 分治（线段树） TODO