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

 

 使用动态规划的解法(来自牛客网)
 
 

 F（i）：以array[i]为末尾元素的子数组负数的和的最大值，子数组负数的元素的相对位置不变
 
 

 
 

 res：所有子数组负数的和的最大值
 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 

 另一个解法具有异曲同工之妙，但效率更高些；