当前位置:网站首页>力扣152题乘数最大子数组
力扣152题乘数最大子数组
2022-07-06 09:22:00 【ai其实很简单】
152.乘数最大子数组
问题描述: 给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
策略: 本题为动态规划的题,可以自底向上的求解答案,遍历整个数组计算当前的最大值用imax进行记录,不断更新最终求解出答案。由于数组中有负数,会将最大值变为最小值,最小值变成最大值,所以需要imin进行记录最小值。当求第i个数时:若该点的值为正数,则该点的最大值可能为前一个数的最大值乘该点的值,或者是该点的值(imax=fmax(imaxnums[i],nums[i]))最小值为(imin=fmin(iminnums[i],nums[i]););若该点的值为负数,将最大值与最小值进行交换,再进行求解。
代码:
int maxProduct(int* nums, int numsSize){
int imax=1,imin=1,max=INT_MIN;
for(int i=0;i<numsSize;i++){
if(nums[i]<0){
//当遇见负数的时候最大值会变成最小值,最小值变成最大值 此时交换位置
int temp=imin;
imin=imax;
imax=temp;
}
imax=fmax(imax*nums[i],nums[i]);
imin=fmin(imin*nums[i],nums[i]);
max=fmax(max,imax); //过去的最大值与该点的最大值进行比较
}
return max;
}
边栏推荐
- FAQs and answers to the imitation Niuke technology blog project (III)
- 【九阳神功】2017复旦大学应用统计真题+解析
- Using spacedesk to realize any device in the LAN as a computer expansion screen
- 5. Function recursion exercise
- 2.C语言初阶练习题(2)
- MySQL事务及实现原理全面总结,再也不用担心面试
- . Net6: develop modern 3D industrial software based on WPF (2)
- 魏牌:产品叫好声一片,但为何销量还是受挫
- 1.C语言矩阵加减法
- PriorityQueue (large root heap / small root heap /topk problem)
猜你喜欢
3.猜数字游戏
魏牌:产品叫好声一片,但为何销量还是受挫
4.二分查找
MySQL锁总结(全面简洁 + 图文详解)
(original) make an electronic clock with LCD1602 display to display the current time on the LCD. The display format is "hour: minute: Second: second". There are four function keys K1 ~ K4, and the fun
FAQs and answers to the imitation Niuke technology blog project (III)
4.分支语句和循环语句
5.函数递归练习
[面試時]——我如何講清楚TCP實現可靠傳輸的機制
Cookie和Session的区别
随机推荐
Mode 1 two-way serial communication is adopted between machine a and machine B, and the specific requirements are as follows: (1) the K1 key of machine a can control the ledi of machine B to turn on a
Implementation of count (*) in MySQL
Differences among fianl, finally, and finalize
9. Pointer (upper)
5月27日杂谈
Cookie和Session的区别
5. Download and use of MSDN
Floating point comparison, CMP, tabulation ideas
Why use redis
1. C language matrix addition and subtraction method
Leetcode. 3. Longest substring without repeated characters - more than 100% solution
优先队列PriorityQueue (大根堆/小根堆/TopK问题)
扑克牌游戏程序——人机对抗
自定义RPC项目——常见问题及详解(注册中心)
Read only error handling
(original) make an electronic clock with LCD1602 display to display the current time on the LCD. The display format is "hour: minute: Second: second". There are four function keys K1 ~ K4, and the fun
7-11 机工士姆斯塔迪奥(PTA程序设计)
重载和重写的区别
Redis cache obsolescence strategy
[modern Chinese history] Chapter 6 test