`

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

 
阅读更多
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])

 

 

分享到:
评论

相关推荐

    40.连续子数组的最大和1

    连续子数组的最大和是动态规划中的一个经典问题,它们要求我们在给定的数组中找到一个连续的子数组,使得该子数组的和最大。这种问题的解决方法有很多,我们今天将介绍两种不同的方法来解决这个问题。 方法一:贪心...

    Java最大子数组和.zip

    最大子数组和是一道经典的算法问题,其目的是在一个数组中找到一个连续的子数组,使得该子数组的和最大。最大子数组和问题可以通过动态规划算法来解决,时间复杂度为O(n),其中n为数组长度。 最大子数组和的具体...

    计算机算法分析与设计最大连续子序列

    该代码使用 scanf 函数读取输入数据,使用 for 循环来遍历数组,使用 if 语句来判断最大和和历史最大的和,并记录最大连续子序列的起始和结束位置。最后,使用 printf 函数输出最大和、最大连续子序列的第一个和最后...

    用C语言实现数组元素最大值/最小值查找、数组元素平均值计算、数组元素排序等功能

    利用C语言可以实现对数组的各种操作,如输入数组元素,输出数组元素、求数组元素平均值、输出数组元素最大值、输出数组元素最小值、查找某数值元素是否存在、给数组元素排序等功能。本压缩文件中是上述功能对应的...

    动态规划算法解决最大子段和和电路布线

    这是一个经典的算法问题,目标是在一个整数数组中找到具有最大和的连续子数组。动态规划解决方案的核心思想是维护两个变量:`max_current`和`max_global`。`max_current`表示到当前位置为止的最大子段和,而`max_...

    最大字段和问题

    最大字段和问题,也常被称为“最大子序列和”或“连续子数组最大和”,是计算机科学中的一个经典算法问题,特别是在数据结构和算法的学习中占有重要地位。它要求从一个给定的整数数组中找出一个连续子数组,使得其...

    Java实现求子数组和的最大值算法示例

    最后,我们输出了最大和和对应的子数组的起始和结束位置。 这个算法的时间复杂度为O(n),其中n是数组的长度。空间复杂度为O(1),因为我们只使用了几个变量来记录相关信息。 此外,本文还提供了一些相关的Java算法...

    如何求连续几个数之和的最大值

    并且,如果有多个连续子数组具有相同的最大和,我们需要选择第一个这样的子数组。这个问题可以通过维护一个滑动窗口的最大和来解决。 这里提供的C++代码实现了一个名为`GetMaxs`的函数,它接收一个整数数组`arrary`...

    C语言程序设计-编写程序。从键盘读入8个整数存入数组a中并输出这8个数据。和、最大值、最小值及平均值。正数之和、负数之和

    从键盘读入8个整数存入数组a中并输出这8个数据。 ⑴求出这8个数据的和、最大值、最小值及平均值。 ⑵求这8个数据的正数之和、负数之和(或正数与负数的个数); ⑶求这8个数据的奇数之和、偶数之和(或奇数与偶数的...

    动态规划最大子序列和 Gabe

    这是因为,在这种情况下,最大连续子序列不存在,因此我们不能输出最大和和最大连续子序列的第一个和最后一个元素。 动态规划最大子序列和问题是一种经典的动态规划问题,可以使用动态规划算法来解决。这类问题在...

    求一矩阵中子矩阵的最大和

    在实际编程实现时,可以使用一个二维数组(或一维数组,根据实现方式)来存储行最大和和列最大和。在处理大型矩阵时,这个算法具有较高的效率,因为它只需要一次遍历,避免了重复计算和回溯。 总结,"求一矩阵中子...

    小学奥数积最大及和最小的规律PPT课件.pptx

    这篇PPT课件主要探讨了两个数学规律:积最大规律和和最小规律,这两个概念在小学奥数中具有重要意义,特别是在解决优化问题时。我们首先来看积最大规律。 积最大规律指出,在多个数的和固定不变的情况下,这些数越...

    列表输出最大值、最小值和和值.py

    列表输出最大值、最小值和和值.

    Java_int、double型数组常用操作工具类(分享)

    该工具类提供了多种常用的数组操作方法,包括获取数组的最大值、最小值、最大值的下标、最小值的下标、数组的和、平均值、打印数组、选择排序对数据进行降序排序和升序排序等。 一、数组的基本操作 在 Java 语言中...

    最大和算法

    在理解最大和算法之前,我们需要了解几个关键的概念:因子图和和积算法(Sum-Product Algorithm)。 ##### 1. 因子图 因子图是一种特殊的有向无环图,用于表示概率模型中的因子(或函数)与变量之间的关系。因子图...

    逆序对(树状数组) C语言

    它的核心思想是将线性数组划分成若干个子区间,每个子区间对应一颗小树,通过这些小树来维护区间的信息。在树状数组中,查询和更新操作的时间复杂度都能达到O(logN),使得它在处理动态区间问题时效率极高。 C语言是...

    数据结构之树状数组讲解

    差分数组是一种特殊的树状数组,可以快速地计算区间的和和差异。我们可以使用 Sigma 函数来计算数组中 1 到 x 的和。 long long Sigma(long long *arra,long long x) //数组中 1 到 x 的和 { long long ans=0; ...

    max_batch.rar_batch

    给定一个整数数组,我们的目标是找到一个连续的子数组(子序列),使得其所有元素之和最大。例如,对于数组[-2, 1, -3, 4, -1, 2, 1, -5, 4],最大子序列和是6,对应的子数组是[4, -1, 2, 1]。 解决这个问题的经典...

    关于区间操作查找(前缀和与差分)+树状数组基础.doc

    关于区间操作查找(前缀和与差分)+树状数组基础 本文主要介绍了前缀和与差分的概念,以及树状数组的基础知识。前缀和是一种数组中某元素之前(包括此元素)的所有元素的和,可以用来快速计算区间和。差分是将当前...

    学习资料课件 PPT 分享

    前缀和以及前缀乘积.pdf**:这部分内容可能讨论数组的前缀和,即数组中连续子数组的累加和,以及前缀乘积,即数组中连续子数组的乘积。可能涉及快速计算前缀和和前缀乘积的算法,如动态规划。 7. **中级篇:堆.pdf...

Global site tag (gtag.js) - Google Analytics