欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

关于连续子数组的最大和和最大积

程序员文章站 2022-05-22 13:35:21
...
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

    这道题目,我没有做出来,想错了,以为求A[i] 的 max和,就是求出A[i-1] ,然后再拿A[i]比较,就是了,但是

   这样的话,对于数组,比如{8,-19,5,-4,20} ,那么Max(4) = 8 , Max(5) = 20 , 但是还有更大的子串{5,-4, 20} 不能得到,因为我是前一个的最大子串来计算的。

   这样不可以的。 

   参考了DISCUSS中的方法,通过引入临时和sum,

   基本思想就是:如果当前和为负数,后面的数值加上当前和则必然小于原数值,则应将当前和丢弃。

   注意这里考虑的是当前和是否为负而不是当前值!

    只要你不小于0,那么对于以后求和,都是增加的!同样,不要担心与负数相加,会减少我们的最大值,

    因为最大值,是存在result中,最后是要与他比较来确定最大值。

    写到这里,我觉得我有点明白这个题目的子问题在哪里了,sum(n - 1) 就是他的子问题。

    通过sum(n-1) ,我们可以求得sum(n) , 然后sum(n) 与 result比较,得到result.

    递推公式:  

sum = Max(sum + A[i], A[i]);
global[i + 1] = Max(sum, global[i]);
public int maxSubArray(int[] A) {
   int sum = A[0];
   int result = A[0];

   for(int i = 1; i < A.length; i++){
       sum = Math.max(sum + A[i] , A[i]);
       result = Math.max(result, sum);
   }

   return result;

}
}

 

  最大积问题:

    思路 : 同样子问题也是sum(n-1) , 但是这次不同,因为存在负数与负数相乘 , 比如{1,-2,3,4,-5};

    解决的办法,维持一个MaxSum, 和 MinSum , 因为前n-1个元素中,存在一个负数的话,那么最小值必然就是它与其他值的乘积。

    然后求max 的时候,就拿这个minSum * arr[n] 与 maxSum*arr[n] ,arr[n] 比较,取的最大值,再与result比较。

    通过维持一个最大数组记录i 位置时的最大值,维持一个最小数据记录i 位置的最小值!

    这样的话,当arr[i]为负时,我就能通过检测最小值与它相乘看是否大于之前的最大值,这就解决了负负相乘可能大于max的问题

  递推式:

// i 位置最大值的拷贝
max_copy[i] = max_local[i] 
//第一个max取得最大值与A[i]相乘结果与A[i]比较,然后再拿最小值与A[i]相乘
max_local[i + 1] = Max(Max(max_local[i] * A[i], A[i]),  min_local * A[i])
min_local[i + 1] = Min(Min(max_copy[i] * A[i], A[i]),  min_local * A[i])