如何用Java求子数组的最大和
这篇文章主要讲解了“如何用Java求子数组的最大和”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“如何用Java求子数组的最大和”吧!
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 因为时间复杂度为O(n), 以为着我们只能有for循环,不能有嵌套for循环;===》 我们只能从语义上去分析这个题目的破绽。
static void maxSubArraySum3(int[] a){ //略去参数检查 boolean allNegative=true; int len=a.length; int[] p=new int[len]; for(int i=0;i<len;i++){ if(allNegative){ if(a[i]>0){ allNegative=false; } } if(i==0){ p[0]=a[0]; }else{ p[i]=p[i-1]+a[i]; } } if(allNegative){ System.out.println("maxSubArraySum=0"); }else{ int max=p[0]; int min=p[0]; for(int i=0;i<len;i++){ if(p[i]>max){ max=p[i]; } if(p[i]<min){ min=p[i]; } } System.out.println("maxSubArraySum="+(max-min)); } }
感谢各位的阅读,以上就是“如何用Java求子数组的最大和”的内容了,经过本文的学习后,相信大家对如何用Java求子数组的最大和这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!