这题如果没有负数和0,答案就很简单了,所有数的乘积。有负数和0就要复杂一些。
-
先考虑只有正数和负数而没有 0 的情况:
- 负数是偶数个。答案也很简单,所有数的乘积。
- 负数是奇数个。那就要枚举这个负数位置,将序列分成两部分,取乘积大的那部分。
-
然后再考虑数据中有 0 的情况,这时我们可以将整个序列以 0 进行分割成多个子序列,每个子序列的处理和情况 1 一样。
class Solution { public: int noZero(int A[], int start, int end) { // 没有 0 的子序列 int ans = A[start], left = 1, right = 1, negCnt = 0; for(int i = start; i <= end; ++i) { right *= A[i]; if(A[i] < 0) { negCnt++; // 计数负数的个数 } } if(negCnt&1) { // 奇数个负数 for(int i = start; i < end; ++i) { left *= A[i]; right /= A[i]; ans = max(max(left, right), ans); } } else { // 偶数个负数 ans = right; } return ans; } int maxProduct(int A[], int n) { int ans = A[0], start = 0, end = 0, i = 0, hasZero = 0; while(i < n) { while(i < n && A[i] == 0) { i++; hasZero = 1; // 标记数据中有 0 } start = i; while(i < n && A[i] != 0) { i++; } end = i - 1; if(end >= start) { // 以 0 分割成多个子串 int tmp = noZero(A, start, end); if(tmp > ans) { ans = tmp; } } } if(hasZero && ans < 0) { ans = 0; } return ans; } };
相关推荐
LeetCode Maximum Product of Word Lengths 完整C++代码,本人使用linux下的g++编译
easy_Maximum-Subarray 提交链接 / Submit (You need register/login first before submit.) (在提交前你需要先注册或登录) 题目描述 / Description Given an integer array nums, find the contiguous subarray ...
动态规划——最大连续子序列和一维最大连续子序列和[x] LeetCode 53 Maximum Subarray设$d[i]$表示以序列中$s[i]$结尾的最大
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
318| [Maximum Product of Word Lengths](https://leetcode.com/problems/maximum-product-of-word-lengths/) | [C++](./C++/maximum-product-of-word-lengths.cpp) [Python](./Python/maximum-product-of-word-...
技巧积累异或的性质: 如果a ^ b = c,则a ^ c = b求最大/最小异或值,可以考虑Trie classic problem: leetcode-421.... Maximum Subarray leetcode-992. Subarrays with K Different Integers单调双端加速度-单队列技
对于每一道算法题会总结代码、时间复杂度以及一些好的blog排序(sort)数组(...SubarrayLeetCode 152 Maximum Product SubarrayLintCode 138 Subarray SumLintCode 139 Subarray Sum ClosestLeetCode 392 Is Subseq
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
大佬的leetcode刷题笔记(c++版本)
vs code LeetCode 插件
leetcode中文版
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...