《编程之美》里面对求一维,二维的都进行了讲解。
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平面。。
同样,四维就分为两个三维来做。。。
分享到:
相关推荐
.求子数组的最大和 题目: 输入一个整形数组,...求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此输出为该子数组的和18。
给定一个二维数组,由其中若干邻近元素构成的矩形称为子数组,请编写程序计算所有子数组元素之和的最大值。 【输入数据】第一行是一个整数N,表示二维数组的大小为N*N。接下来的N*N个数被空格和换行符隔开,表示按照...
给定一个二维数组,由其中若干邻近元素构成的矩形称为子数组,请编写程序计算所有子数组元素之和的最大值。 【输入数据】第一行为整数N,代表二维数组的大小为N*N。接下来的N*N个整数被空格和换行符隔开,表示按照行...
利用C语言可以实现对数组的各种操作,如输入数组元素,输出数组元素、求数组元素平均值、输出数组元素最大值、输出数组元素最小值、查找某数值元素是否存在、给数组元素排序等功能。本压缩文件中是上述功能对应的...
在JavaScript中可以通过内置的 Math.max() 的最大值,但是要从多重数组中取出最大值,还是有一定的难度。 问题描述 假设你有一个数组,而且这个数组中包含了数字的子数组,而我们要做的是从数组中的每个子数组中返回...
求数组的子数组之和的最大值,数组中全部为整数,子数组之和即为连续的数组元素相加之和
分治思想:将难以直接求解的大问题分解为k个相同的子问题;对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止;
NULL 博文链接:https://eleopard.iteye.com/blog/1564692
题目描述: 一个有 n 个元素的数组,这 n 个元素既可以是正数也可以是...找出所有的子数组,然后求出子数组的和,在所有子数组的和中取最大值。 代码实现: #!/usr/bin/env python3 # -*- coding: utf-8 -*- # @Time
java代码-使用java解决输出数组中加起来最大两个元素的值的源代码 ——学习参考资料:仅用于个人学习使用!
给一个数组,返回它的最大连续子序列的和使用动态规划F(i):以array[i]为末尾元素的子数组的和的最大值,子数组的元素的相对位置不变res:所有子数组的和的
给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字)。 2、代码详解 法一:可扩展性好(推荐) 二维数组,2*2大小,一维存最大值,一维存负最大值 class Solution(object)...
主要介绍了Java实现求子数组和的最大值算法,涉及Java数组遍历、判断、运算等相关操作技巧,需要的朋友可以参考下
在一个数组中找出连续元素的最大值,时间复杂度o(n),空间复杂度o(n)
关于连续子数组最大和这个问题,有两种解法,一种是动态规划 解法如下: function getMaxSubSum($arr){ $curSum = $arr[0]; $maxSum = $arr[0]; for($i = 1; $i < count($arr); $i++){ if
java代码-使用java计算NxN整型数组中最大值(假定唯一)所在行的和与最大值所在列的和的源代码 ——学习参考资料:仅用于个人学习使用!
求所有子数组的和的最大值,要求时间复杂度为O(n)例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。思路记
在数组中,数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5, 11, 9}中,数对之差的最大值是11,是16减去5的结果。
要求:找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和,要求时间复杂度为 O(n)。即将之前累加和加上当前值与当前值做比较, 如果将之前累