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])
相关推荐
最大子数组和是一道经典的算法问题,其目的是在一个数组中找到一个连续的子数组,使得该子数组的和最大。最大子数组和问题可以通过动态规划算法来解决,时间复杂度为O(n),其中n为数组长度。 最大子数组和的具体...
利用C语言可以实现对数组的各种操作,如输入数组元素,输出数组元素、求数组元素平均值、输出数组元素最大值、输出数组元素最小值、查找某数值元素是否存在、给数组元素排序等功能。本压缩文件中是上述功能对应的...
动态规划算法解决最大子段和和电路布线 算法是《计算机算法设计与分析》上的,我只是加了些界面。
从键盘读入8个整数存入数组a中并输出这8个数据。 ⑴求出这8个数据的和、最大值、最小值及平均值。 ⑵求这8个数据的正数之和、负数之和(或正数与负数的个数); ⑶求这8个数据的奇数之和、偶数之和(或奇数与偶数的...
列表输出最大值、最小值和和值.
硬判决和和积译码的性能相差不大,而最大似然译码的性能较好。因为最大似然译码的方法是找出所有发送码字中可能性最大的发送码字作为译码估值,是一种通过经验与归纳,由接收值推测发送码字的方法。
使用自底向上方法实现的最大子数组 使用动态规划的两种方式实现的LCS(最大公共串)(下面的算法都会使用动态规划的两种方式来实现) 加权有向无环图中最短路径和最长路径 背包问题 最长回文子串(lps) ###幂乘:算法...
汇编课程设计 求1~5000之间的所有素数 有源代码,有报告,超全~~
一道期末题~关于双精度浮点数的加和和乘积,从键盘录入所输入的数,有异常环节,可以查出错误并且指出原因。
AutoTextViewSample两种方法,数组在代码和和数组在XML中。
第一部分 微机原理及汇编程序设计 实验一、认识Tddebug集成操作软件实验二、I/O程序设计 实验三、分支程序设计实验四、循环程序设计实验五、运算类程序设计………………………………………………15 ...
1.04 浮动和和盒模型
【作品名称】:基于TMS320F28027制作太阳能充电和和逆变装置-光能手机万能充电器(论文+源程序+电路图) 【适用人群】:适用于希望学习不同技术领域的小白或进阶学习者。可作为毕设项目、课程设计、大作业、工程实...
由于内存和处理能力有限,很难在Arduino上从音频信号中检测音乐音符。通常,音符不是纯正弦波,因此很难检测。如果我们对各种乐器进行频率变换,则基于正在演奏的音符,它可能包含多个谐波。每个乐器都有其自己的...
设计封面和和封底.通俗易懂,好学好用,运用广泛。
基于和积算法的LDPC码译码算法,采用的是7/4线性分组码,但是这里程序是灵活的,可以替换为任意形式的LDPC码。还有一个书面的报告,详细的解释了译码过程和和积算法原理,希望对大家有帮助
在本篇文章里小编给大家分享了关于Python中整数的最大值输出的实例内容,以及相关知识点,需要的朋友们学习下。
用java写的找出1到100的所有素数和和数,并输出来
和和公司食品安全手册.doc
和和公司食品安全手册.pdf