【Leetcode】152. 乘积最大子数组
2021/4/24 10:25:21
本文主要是介绍【Leetcode】152. 乘积最大子数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
// 152. 乘积最大子数组 // 给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少 // 包含一个数字),并返回该子数组所对应的乘积。
题解
// 动态规划 // 本题目如果参考最大子串和的话,初始化中途遍历子串的最大乘积tempMax=1, // for循环遍历nums元素,记为nums[i]。 // 如果tempMax对nums[i]有增益(tempMax非负数),则将tempMax与nums[i]累乘赋 // 给tempMax,如果tempMax对nums[i]没有增益(tempMax为负数),则子串截断, // 直接将nums[i]赋给tempMax。所以简单说就是选取tempMax*nums[i]和nums[i] // 中最大值赋给tempMax:tempMax=Math.max(tempMax*nums[i], nums[i])。 // 到此为止都还好理解。我们就有如下解法: class Solution { public int maxProduct(int[] nums) { if (nums.length == 0) return 0; int res = Integer.MIN_VALUE; int tempMax = 1; for (int i = 0; i < nums.length; i++) { tempMax = Math.max(tempMax * nums[i], nums[i]); res = Math.max(res, tempMax); } return res; } } // 但是如果tempMax连续遇到2个负数呢?负负得正,其实这两个负数反过来会对 // 之后的累乘有增益!但我们的机制却已经把乘了第一个负数时的tempMax给去除了, // 说明我们还需要记录tempMax为负数的情况。 // 记录中途遍历子串的最小乘积tempMin,初始化为1,tempMax记录中途遍历子串的 // 最大乘积,那tempMin专门记录中途遍历子串的最小乘积,一旦遇到负数nums[i], // 直接将tempMin和tempMax交换, 这时候再和nums[i]相乘,原来的子串的最小乘 // 积tempMin就变成了子串最大乘积,如果连续遇到两个负数,出现负负得正的情况, // 则可以利用tempMax tempMin遇负交换的机制,来囊括到这种情况。 // // 执行用时:2 ms, 在所有 Java 提交中击败了88.66%的用户 // 内存消耗:38.2 MB, 在所有 Java 提交中击败了67.19%的用户 class Solution { public int maxProduct(int[] nums) { if (nums.length == 0) return 0; int res = Integer.MIN_VALUE; int tempMax = 1; int tempMin = 1; for (int i = 0; i < nums.length; i++) { if (nums[i] < 0) { int temp = tempMax; tempMax = tempMin; tempMin = temp; } if (nums[i] >= 0) { tempMax = Math.max(tempMax * nums[i], nums[i]); tempMin = Math.max(tempMin * nums[i], nums[i]); } res = Math.max(res, tempMax); } return res; } }
这篇关于【Leetcode】152. 乘积最大子数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验