题目描述:
HZ 偶尔会拿些专业问题来忽悠那些非计算机专业的同学. 今天测试组开完会后, 他又发话了: 在古老的一维模式识别中, 常常需要计算连续子向量的最大和, 当向量全为正数的时候, 问题很好解决. 但是, 如果向量中包含负数, 是否应该包含某个负数, 并期望旁边的正数会弥补它呢? 例如:{6,-3,-2,7,-15,1,2,2}, 连续子向量的最大和为 8(从第 0 个开始, 到第 3 个为止). 给一个数组, 返回它的最大连续子序列的和, 你会不会被他忽悠住?(子向量的长度至少是 1)
解题思路:
这种求最大最小的问题, 想到用 dp. 这题其实也是 dp 比较经典的题.
设一个 dp 数组, 大小和输入序列长度一致. 例如序列为 {6,-3,-2,7,-15,1,2,2}, 那么 dp 的指就为 max(array[i], array[i]+dp[i-1]).
时间复杂度为 O(n).
代码:
- class Solution {
- public:
- int FindGreatestSumOfSubArray(vector<int> array) {
- if(array.size()==1)
- return array[0];
- int dp[array.size()];
- for(int i=0; i<array.size(); i++)
- {
- if(i==0)
- dp[i] = array[i];
- else
- {
- if(array[i]>=dp[i-1]+array[i])
- {
- dp[i] = array[i];
- }
- else
- {
- dp[i] = dp[i-1]+array[i];
- }
- }
- }
- int max_sum = INT_MIN;
- for(int i=0; i<array.size(); i++)
- {
- if(max_sum<dp[i])
- max_sum = dp[i];
- }
- return max_sum;
- }
- };
来源: http://www.bubuko.com/infodetail-3004345.html