最大连续子数组的积
不考虑溢出,注意多个0,多个负数,还有结果是1的情况
public class MaxSubMultiplication { public static int calculate(int[] array) { int lastZeroIndex = -1; int indexOfFirstNegative = -1; int indexOfLastNegative = -1; int mulBeforeFirst = 1; int mulAfterLast = 1; int mulOfAll = 1; boolean hasPositive = false; int max = 0; for (int i = 0; i < array.length; i++) { if (array[i] == 0) { if (mulOfAll > 0) { if (max < mulOfAll) max = mulOfAll; } else if (mulOfAll < 0) { for (int j = lastZeroIndex + 1; j <= indexOfFirstNegative - 1; j++) { mulBeforeFirst *= array[j]; } for (int k = indexOfLastNegative + 1; k <= i - 1; k++) { mulAfterLast *= array[k]; } int cadidateOne = (mulOfAll / mulBeforeFirst) / array[indexOfFirstNegative]; int cadidateTwo = (mulOfAll / mulAfterLast) / array[indexOfLastNegative]; int result = maxOfFour(mulBeforeFirst, mulAfterLast, cadidateOne, cadidateTwo); if (max < result) max = result; } lastZeroIndex = i; indexOfFirstNegative = -1; indexOfLastNegative = -1; mulBeforeFirst = 1; mulAfterLast = 1; mulOfAll = 1; } else { if (array[i] < 0) { if (indexOfFirstNegative < 0) indexOfFirstNegative = i; indexOfLastNegative = i; } mulOfAll *= array[i]; if (mulOfAll > 0 || array[i] > 0) hasPositive = true; } } if (mulOfAll > 0) { if (max < mulOfAll) max = mulOfAll; } else if (mulOfAll < 0) { for (int j = lastZeroIndex + 1; j <= indexOfFirstNegative - 1; j++) { mulBeforeFirst *= array[j]; } for (int k = indexOfLastNegative + 1; k <= array.length - 1; k++) { mulAfterLast *= array[k]; } int cadidateOne = (mulOfAll / mulBeforeFirst) / array[indexOfFirstNegative]; int cadidateTwo = (mulOfAll / mulAfterLast) / array[indexOfLastNegative]; int result = maxOfFour(mulBeforeFirst, mulAfterLast, cadidateOne, cadidateTwo); if (max < result) max = result; } return (max != 1) ? max : (hasPositive ? max : 0); } private static int maxOfFour(int a, int b, int c, int d) { int max = a; if (max < b) max = b; if (max < c) max = c; if (max < d) max = d; return max; } public static void main(String[] args) { int[] array = { -1, 0, -2, 1, 0, -6, 0, -7 }; System.out.println(MaxSubMultiplication.calculate(array)); } }
相关推荐
从头到尾逐个累加示例数组中的每个数字。初始化和为0,第一步加上第一个数字1,...第八步加上最后一个数字-5,由于得到的和为13,小于此前最大和18,因此最终最大的子数组的和为18,对应的子数组是{3,10,-4,7,2}。
求元素组合成连续子数组之和最大的子数组,要求时间复杂度为O(n)
求最大连续子数组.cpp
一个整数数组中的元素有正有负,在该数组中找出一个连续子数组,要求该连续子数组中各元素的和最大,这个连续子数组便被称作最大连续子数组。 随机产生1000以上的数据(有正有负),写入文件input.txt 比如数组{2,4,...
最大和连续子数组比较熟悉贴个文章http://en.wikipedia.org/wiki/Maximum_subarray_problem。
连续子数组的最大和.md
40.连续子数组的最大和1
最短无序连续子数组给你一个整数数组 nums ,你需要找出一个 连续子数组 ,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。//从前向后遍历记录排
java基础面试题连续子数组的最大和本资源系百度网盘分享地址
连续子数组的最大和输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。解题思路:动态规划Dp[i]表示 nums 中以 nums[i]结尾的最大子数组和
给定一个整形数组和一个数字s,找到数组中最短的一个连续子数组,使得连续子数组的数字和sum>=s,返回这个最短的连续子数组的长度值public int minS
42. 连续子数组的最大和题目描述{6, -3, -2, 7, -15, 1, 2, 2},连续子数组的最大和为 8(从第 0 个开始,到第 3 个为止)。
主要介绍了Python语言描述连续子数组的最大和,具有一定借鉴价值,需要的朋友可以参考下
给定一个二维数组,由其中若干邻近元素构成的矩形称为子数组,请编写程序计算所有子数组元素之和的最大值。 【输入数据】第一行为整数N,代表二维数组的大小为N*N。接下来的N*N个整数被空格和换行符隔开,表示按照行...
主要介绍了python求最大连续子数组的和,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此...
自己写的分治算法,也包括了暴力求解的部分,并比较两者的运行时间,输出最大子数组的起始位置
要求:找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和,要求时间复杂度为 O(n)。即将之前累加和加上当前值与当前值做比较, 如果将之前累
js代码-200605-连续子数组的最大和