分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.ArrayAndMatrix; /** * 数组中子数组的最大累乘积 * * 【题目】 * 给定一个double类型的数组arr其中的元素可正、可负、可0返回子数组累乘的最大乘积。例如 * arr[-2.5,4,0,3,0.5,8,-1]子数组[3,0.5,8]累乘可以获得最大的乘积12所以返回12。 * * 【难度】 * 中等 * * 【解答】 * 本题可以做到时间复杂度为O(N)、额外空间复杂度为O(1)。所有的子数组都会以某一个位置结束所以如果求出以每一个位置结尾 * 的子数组最大的累乘积在这么多最大累乘积中最大的那个就是最终的结果。也就是说结果Max{以arr[O]结尾的所有子数组的最 * 大累乘积以arr[1]结尾的所有子数组的最大累乘积...以arr[arr.length-1]结尾的所有子数组的最大累乘积}。 * * 如何快速求出所有以i位置结尾(arr[i])的子数组的最大乘积呢假设以arr[i-1]结尾的最小累乘积为min以arr[i-1]结尾的最 * 大累乘积为max。那么以arr[i]结尾的最大累乘积只有以下三种可能 * •可能是max*arr[i]。max既然表示以arr[i-1]结尾的最大累乘积那么当然有可能以arr[i]结尾的最大累乘积是max*arr[i]。 * 例如[3,4,5]在算到5的时候。 * •可能是min*arr[i]。min既然表示以arr[i-1]结尾的最小累乘积当然有可能min是负数而如果arr[i]也是负数两个负数相乘 * 的结果也可能很大。例如[-2,3,-4]在算到-4的时候。 * •可能仅是arr[i]的值。以arr[i]结尾的最大累乘积并不一定非要包含arr[i]之前的数。例如[0.1,0.1,100]在算到100的时候。 * 这三种可能的值中最大的那个就作为以i位置结尾的最大累乘积最小的作为最小累乘积然后继续计算以i1位置结尾的时候如此重 * 复直到计算结束。 * * 具体过程请参看如下代码中的maxProduct方法。 * * author Created by LiveEveryDay */ public class InArraySubArrayMaxProduct { public static double maxProduct(double[] arr) { if (arr null || arr.length 0) { return 0; } double max arr[0]; double min arr[0]; double res arr[0]; double maxEnd 0; double minEnd 0; for (int i 1; i arr.length; i) { maxEnd max * arr[i]; minEnd min * arr[i]; max Math.max(Math.max(maxEnd, minEnd), arr[i]); min Math.min(Math.min(maxEnd, minEnd), arr[i]); res Math.max(res, max); } return res; } public static void main(String[] args) { double[] arr {-2.5, 4, 0, 3, 0.5, 8, -1}; System.out.printf(The max product is: %.2f, maxProduct(arr)); } } // ------ Output ------ /* The max product is: 12.00 */