当前位置:网站首页>Force deduction 152 question multiplier maximum subarray
Force deduction 152 question multiplier maximum subarray
2022-07-06 13:54:00 【AI is actually very simple】
152. The largest subarray of multipliers
Problem description : Give you an array of integers nums , Please find the non empty continuous subarray with the largest product in the array ( The subarray contains at least one number ), And returns the product of the subarray .
The answer to the test case is 32- position Integers .
Subarray Is a continuous subsequence of an array .
Strategy : This topic is the topic of dynamic programming , You can solve the answer from the bottom up , Traverse the entire array to calculate the current maximum value with imax For recording , Constantly update and finally solve the answer . Because there are negative numbers in the array , Will change the maximum value to the minimum value , The minimum becomes the maximum , So we need to imin Record the minimum value . When seeking the first i Number of hours : If the value of this point is positive , Then the maximum value of this point may be the maximum value of the previous number multiplied by the value of this point , Or the value of this point (imax=fmax(imaxnums[i],nums[i])) The minimum value is (imin=fmin(iminnums[i],nums[i]);); If the value of this point is negative , Exchange the maximum value with the minimum value , Then solve .
Code :
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){
// When a negative number is encountered, the maximum value will become the minimum value , The minimum becomes the maximum Exchange position at this time
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); // Compare the past maximum with the maximum at this point
}
return max;
}
边栏推荐
- Package bedding of components
- 5月14日杂谈
- Leetcode.3 无重复字符的最长子串——超过100%的解法
- (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
- 一段用蜂鸣器编的音乐(成都)
- 甲、乙机之间采用方式 1 双向串行通信,具体要求如下: (1)甲机的 k1 按键可通过串行口控制乙机的 LEDI 点亮、LED2 灭,甲机的 k2 按键控制 乙机的 LED1
- Programme de jeu de cartes - confrontation homme - machine
- 8. C language - bit operator and displacement operator
- 实验七 常用类的使用(修正帖)
- 强化学习基础记录
猜你喜欢
随机推荐
About the parental delegation mechanism and the process of class loading
PriorityQueue (large root heap / small root heap /topk problem)
JS several ways to judge whether an object is an array
简述xhr -xhr的基本使用
实验九 输入输出流(节选)
Using spacedesk to realize any device in the LAN as a computer expansion screen
Analysis of penetration test learning and actual combat stage
[the Nine Yang Manual] 2019 Fudan University Applied Statistics real problem + analysis
Have you encountered ABA problems? Let's talk about the following in detail, how to avoid ABA problems
使用Spacedesk实现局域网内任意设备作为电脑拓展屏
FAQs and answers to the imitation Niuke technology blog project (I)
SRC mining ideas and methods
扑克牌游戏程序——人机对抗
附加简化版示例数据库到SqlServer数据库实例中
[the Nine Yang Manual] 2020 Fudan University Applied Statistics real problem + analysis
仿牛客技术博客项目常见问题及解答(一)
Leetcode. 3. Longest substring without repeated characters - more than 100% solution
编写程序,模拟现实生活中的交通信号灯。
这次,彻底搞清楚MySQL索引
【educoder数据库实验 索引】