判断数组是否全为0_连续子数组的最大和的解题思路及代码方法一_动态规划

题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢&＃xff1f;例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组&＃xff0c;返回它的最大连续子序列的和&＃xff0c;你会不会被他忽悠住&＃xff1f;(子向量的长度至少是1)

示例

输入&＃xff1a;

[1,-2,3,10,-4,7,2,-5]

输出&＃xff1a;

18

解题思路及代码

方法一&＃xff1a;动态规划

我们想找出连续子数组的最大和&＃xff0c;很明显我们肯定要尽量选取正数的部分。当某个连续的部分和值为负数&＃xff0c;我们肯定不会选择进去&＃xff0c;因为这一部分肯定会让和值减小。而遇到某个连续部分和值为正数&＃xff0c;我们就应该将这一部分保留&＃xff0c;继续考察。

具体动态规划的方法为&＃xff1a;

状态定义&＃xff1a;dp[i]表示以i结尾的连续子数组的最大和。所以最终要求dp[n-1]

状态转移方程&＃xff1a;dp[i] &＃61; max(array[i], dp[i-1]&＃43;array[i])

解释&＃xff1a;如果当前元素为整数&＃xff0c;并且dp[i-1]为负数&＃xff0c;那么当然结果就是只选当前元素

技巧&＃xff1a;这里为了统一代码的书写&＃xff0c;定义dp[i]表示前i个元素的连续子数组的最大和&＃xff0c;结尾元素为array[i-1]

代码如下&＃xff1a;

时间复杂度&＃xff1a;O(n)

空间复杂度&＃xff1a;O(n)

c&＃43;&＃43;中vector的初始化有五种方式&＃xff0c;举例说明如下&＃xff1a;
&＃xff08;1&＃xff09; vector a(10); //定义了10个整型元素的向量&＃xff08;尖括号中为元素类型名&＃xff0c;它可以是任何合法的数据类型&＃xff09;&＃xff0c;但没有给出初值&＃xff0c;其值是不确定的。
&＃xff08;2&＃xff09;vector a(10,1); //定义了10个整型元素的向量,且给出每个元素的初值为1
&＃xff08;3&＃xff09;vector a(b); //用b向量来创建a向量&＃xff0c;整体复制性赋值
&＃xff08;4&＃xff09;vector a(b.begin(),b.begin&＃43;3); //定义了a值为b中第0个到第2个&＃xff08;共3个&＃xff09;元素 &＃xff08;5&＃xff09;int b[7]&＃61;{1,2,3,4,5,9,8};
vector a(b,b&＃43;7); //从数组中获得初值

方法二&＃xff1a;对方法一的优化&＃xff0c;降低空间复杂度

思想很简单&＃xff0c;就是对下标为i的元素array[i]&＃xff0c;先试探的加上array[i], 如果和为负数&＃xff0c;显然&＃xff0c;以i结尾的元素对整个结果不作贡献。 具体过程&＃xff1a;

1. 初始化&＃xff1a;维护一个变量tmp &＃61; 0
2. 如果tmp&＃43;array[i] <0, 说明以i结尾的不作贡献&＃xff0c;重新赋值tmp &＃61; 0
3. 否则更新tmp &＃61; tmp &＃43; array[i] 最后判断tmp是否等于0&＃xff0c; 如果等于0&＃xff0c; 说明数组都是负数&＃xff0c;选取一个最大值为答案。

代码如下&＃xff1a;

时间复杂度&＃xff1a;O(n)

空间复杂度&＃xff1a;O(1)

另外&＃xff0c;类似思想使用 Java 的代码为&＃xff1a;