给定一个整型数足a,求出最大连续子段的乘积,比如 1, 2, -8, 12, 7则输出12 * 7 = 84
代码如下:
// maxProduct.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
// 子数组的最大乘积
int MaxProduct(int *a, int n)
{
int maxProduct = 1; // max positive product at current position
int minProduct = 1; // min negative product at current position
int r = 1; // result, max multiplication totally
for (int i = 0; i < n; i++)
{
if (a[i] > 0)
{
maxProduct *= a[i];
minProduct = min(minProduct * a[i], 1);
}
else if (a[i] == 0)
{
maxProduct = 1;
minProduct = 1;
}
else // a[i] < 0
{
int temp = maxProduct;
maxProduct = max(minProduct * a[i], 1);
minProduct = temp * a[i];
}
r = max(r, maxProduct);
}
return r;
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[]={1, -2, -3,0,5};
int result = MaxProduct(a,5);
cout<<result<<endl;
system("pause");
return 0;
}
分享到:
相关推荐
算法 子数组最大乘积
给定一个n个元素的数组,数组元素全部为整数,负数,正数和0均有可能存在,设设计一个算法,找出连续的几个数组元素相乘积最大
给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字)。 2、代码详解 法一:可扩展性好(推荐) 二维数组,2*2大小,一维存最大值,一维存负最大值 class Solution(object)...
示例 1:输入: [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。示例 2:输入: [-2,0,-1]输出: 0解释: 结果不能为 2
向您详细介绍微软测试题,相信您一定会有所收获。
乘积最大子数组.md
乘积最大子数组(java代码).docx
Java-Leetcode-乘积最大子数组.zip
python python_leetcode面试题解之第152题乘积最大子数组_题解
javascript javascript_leetcode面试题解动态规划问题之第152题乘积最大子数组_题解
152. 乘积最大子数组public int maxProduct(int[] nums) {//也可以用数组代替//下面mx会改变所以需要先存储起来;//三种
提醒:此最大乘积连续子串与最大乘积子序列不同,请勿混淆,前者子串要求连续,后者子序列不要求连续。也就是说:最长公共子串(Longest CommonSubstring)和最长公共子序列(LongestCommon Subsequence,LCS)的...
示例 1:输入: [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。示例 2:输入: [-2,0,-1]输出: 0解释: 结果不能为 2
最大乘积子阵列 最大子数组 最大和连续子序列 底部的最小距离 最小硬币兑换 最低成本路径 最小分区 最小大小子阵列总和 表示数字的最小平方 最小步数为一 最低票价 最优二叉搜索树 回文分区 棒材切割 ...
leetcode中国数据结构...找到最大乘积子数组 找到最长的连续子序列 给定一个大小为 n 的数组和一个数字 k,找出出现次数超过“n/k”次的所有元素。 最多两次买卖股票的最大利润 判断一个数组是否是另一个数组的子集 找
leetcode中国450 道 DSA 练习题 Sl N0。 题目问题 Array 反转数组 ...查找数组中的最大和最小元素 ...数组查找最大和连续子数组 ...数组查找是否存在总和等于0的子数组 ...数组查找最大乘积子数组 数组查找最
连续子数组最大和32.把数组排出最小的数35.数组中的逆序对37.数字在排序数组中出现的次数40.数组中自出现过一次的数字50.数组中的重复数字51.构建乘积数组 数组篇 1.二维数组中的查找 在一个二维数组中(每个一维...
II实现 Trie (前缀树)单词搜索 II有效的字母异位词字符串中的第一个唯一字符数组Python实现乘积最大子序列多数元素存在重复元素移动零打乱数组两个数组的交集 II递增的三元子序列搜索二维矩阵 II除自身以外数组的...