`
fuhao_987
  • 浏览: 63973 次
  • 性别: Icon_minigender_2
  • 来自: 北京
社区版块
存档分类
最新评论

子数组之和的最大值

 
阅读更多
《编程之美》里面对求一维,二维的都进行了讲解。
1、一维中用动态规划可以使时间复杂度降到O(n).
   思想:考虑数组中A[0],与最大的一段数组(A[i],...A[j])的关系
         (1)、当0=i=j时,元素A[0]本身构成最大的一段
         (2)、当0=i<j时,和最大的一段以 A[0]开始
         (3)、当0<i时,元素A[0]与和最大一段没有关系
   假设已经知道(A[1],...A[n-1])中和最大的一段数组之和为All[1],并且已经知道(A[1],...,A[n-1])中包含A[1]的和最大一段为start[1],那么A[0]到A[n-1]中和最大的一段为max(A[0],A[0]+start[1],All[1])
  
   动态规划总是这样,分析最后的结果,然后累加中间步骤的小结果们。
int max(int x,int y){
    return (x > y) ? x : y;
}
int maxSum(int* A, int n){
    start[n-1] = A[n-1];
    All[n-1] = A[n-1];
    for(i = n-2; i>=0; i--){
        start[i] = max(A[i], A[i]+start[i+1]);
        all[i] = max(start[i],all[i+1]);
    }
}   return all[0];


2、二维中,假设已经确定了矩形区域的上下边界,比如知道矩形区域的上下边界分别是第a行和第c行,现在要确定左右边界。

转化为一个一维问题,可以把每一列中第a行和第c行之间的元素看成一个整体。即求数组(BC[1],...BC[M])中和最大的一段,其中B[i] = B[a][i]+...B[c][i].

3、扩展问题;如果是三维数组呢?
我的问题是如果是高维数组呢?

----------------------------
其实不管多高维,都可以用二维数组的解法来解,三维数组就分解为两个二维平面。。对应于二维中的第a行和第c行,三维中就是第a个平面和第c平面;对应于二维中BC的数组,三维中就是BC平面。。
同样,四维就分为两个三维来做。。。

分享到:
评论

相关推荐

    数组中最大和的子数组

    这个问题的目标是找到数组中的一个连续子数组,使得这个子数组的所有元素之和最大。 首先,我们需要理解什么是子数组。在数组中,子数组是由数组中任意两个下标i和j(i )确定的一段连续元素的集合,即原数组的第i...

    汇编程序 求数组元素的最大值和最小值

    本篇文章将详细探讨如何使用汇编语言编写程序来找出数组中的最大值和最小值。 首先,我们需要了解汇编语言的基本概念。在汇编语言中,我们使用指令来表示计算机的操作,如加载(LOAD)、存储(STORE)、加法(ADD)...

    C语言程序:求子数组的最大和

    .求子数组的最大和 题目: 输入一个整形数组,...求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此输出为该子数组的和18。

    分治算法-求一个数组中的最大值和最小值

    3. **合并**:将两个子数组的最大值和最小值进行比较,从而得出整个数组的最大值和最小值。 #### 三、代码实现详解 下面是具体的代码实现,该程序采用 C 语言编写: ```c #include "stdio.h" #define maxn ...

    求二维数组最大和的子数组

    给定一个二维数组,由其中若干邻近元素构成的矩形称为子数组,请编写程序计算所有子数组元素之和的最大值。 【输入数据】第一行是一个整数N,表示二维数组的大小为N*N。接下来的N*N个数被空格和换行符隔开,表示按照...

    求二维数组的最大和的子数组

    给定一个二维数组,由其中若干邻近元素构成的矩形称为子数组,请编写程序计算所有子数组元素之和的最大值。 【输入数据】第一行为整数N,代表二维数组的大小为N*N。接下来的N*N个整数被空格和换行符隔开,表示按照行...

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

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

    数组最大值最小值_数组最大值最小值_最小值_

    4. **分治法**:对于大型数组,可以使用分治策略,将数组分为两半,递归地找最大值和最小值,然后比较两个子数组的结果。这种方法在数据量大且深度足够的情况下能提高效率。 在实际应用中,为了优化性能,还可以...

    求数组的子数组之和的最大值,转载自:黑梦楠的日志

    标题中的“求数组的子数组之和的最大值”是一个经典的计算机科学问题,通常被称为“最大子序列和”(Maximum Subarray Problem)。这个问题在数组或序列数据结构中寻找一段连续的子序列,使得子序列的所有元素之和...

    JS中取二维数组中最大值的方法汇总

    在JavaScript中可以通过内置的 Math.max() 的最大值,但是要从多重数组中取出最大值,还是有一定的难度。 问题描述 假设你有一个数组,而且这个数组中包含了数字的子数组,而我们要做的是从数组中的每个子数组中返回...

    分治算法实验(用分治法查找数组元素的最大值和最小值).pdf

    该算法的思路是将数组元素大于 2 的数组分成两个子数组,然后对每一个子数组递归调用,直到最小的子数组的元素个数为 1 个或 2 个,此时直接就能得出最大值与最小值,然后合并子数组,比较 2 个子数组的最大值与...

    求子数组最大和

    这个问题的目标是给定一个整数数组,找出这个数组中的一个连续子数组,使得其元素之和最大。这个问题的一个著名解决方案是Kadane's Algorithm(卡丹算法),它具有线性时间复杂度,即O(n),其中n是数组的长度。 ...

    连续最大子数组和1

    在给定的编程问题中,我们正在探讨一个经典的算法问题,称为“连续最大子数组和”(也称为“最大子序列和”)。这个问题源于计算机科学领域,特别是在算法设计和分析中,经常作为面试和竞赛编程的题目出现。LeetCode...

    乘积最大子数组(动态规划)1

    题目 "乘积最大子数组(动态规划)1" 是一道典型的动态规划问题,来源于 LeetCode 平台。问题要求在给定的整数数组 `nums` 中找出乘积最大的连续子数组,并返回这个子数组的最大乘积。动态规划是一种解决复杂问题的...

    分治算法实验(用分治法查找数组元素的最大值和最小值) (2).pdf

    在这个实验中,我们将数组元素分成两个子数组,然后递归调用 merge 函数,直到最小的子数组的元素个数为 1 个或者是 2 个,此时直接就能得出最大值与最小值,然后合并子数组,比较 2 个子数组的最大值与最小值,依次...

    详解数组分段和最大值最小问题python.docx

    数组分段和最大值最小问题,也称为最小 m 段和问题,是一类经典的计算机算法问题,旨在找到一种分割方式,使得将给定的整数序列分割成 m 个连续子序列时,这些子序列和的最大值尽可能小。这个问题在实际应用中有着...

    分治算法实验(用分治法查找数组元素的最大值和最小值).docx

    该算法的思想是将数组元素大于2的数组分成两个子数组,然后对每一个子数组递归调用,直到最小的子数组的元素个数为1个或者是2个,此时直接就能得出最大值与最小值,然后合并子数组,比较2个子数组的最大值与最小值,...

    【华为OD机试真题2023JAVA&JS】几何平均值最大子数组

    每次移动`i`,计算新的子数组的几何平均值,如果大于当前最大值,更新最大值和子数组信息。同时,由于题目要求在多个几何平均值相等的情况下选择长度最小的子数组,因此需要记录当前子数组的长度`len`,以便于比较。...

    用递归算法编写求一个数组A中的最大元素

    通过上述分析可以看出,递归算法在解决数组最大值问题时具有很好的实用性和可读性。虽然递归算法存在一定的局限性,但在处理相对较小的数据集时,其简洁性和直观性使其成为一种非常有用的技术手段。

    c语言入门编程之数组操作子数组最大平均数.zip

    通过以上讲解,你应该能够理解和实现C语言中数组操作子数组最大平均数的问题。记得在实际编程时,确保对数组的边界条件有充分考虑,并合理运用循环和条件判断来实现算法。祝你在C语言的学习之路上更进一步!

Global site tag (gtag.js) - Google Analytics