当前位置:网站首页>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;
}
边栏推荐
- The latest tank battle 2022 full development notes-1
- [dark horse morning post] Shanghai Municipal Bureau of supervision responded that Zhong Xue had a high fever and did not melt; Michael admitted that two batches of pure milk were unqualified; Wechat i
- 实验九 输入输出流(节选)
- Write a program to simulate the traffic lights in real life.
- Inaki Ading
- The difference between overloading and rewriting
- [modern Chinese history] Chapter V test
- String abc = new String(“abc“),到底创建了几个对象
- 简单理解ES6的Promise
- FAQs and answers to the imitation Niuke technology blog project (III)
猜你喜欢
受检异常和非受检异常的区别和理解
Leetcode. 3. Longest substring without repeated characters - more than 100% solution
PriorityQueue (large root heap / small root heap /topk problem)
Nuxtjs quick start (nuxt2)
hashCode()与equals()之间的关系
Principles, advantages and disadvantages of two persistence mechanisms RDB and AOF of redis
Meituan dynamic thread pool practice ideas, open source
canvas基础2 - arc - 画弧线
. Net6: develop modern 3D industrial software based on WPF (2)
2022泰迪杯数据挖掘挑战赛C题思路及赛后总结
随机推荐
Intensive literature reading series (I): Courier routing and assignment for food delivery service using reinforcement learning
Matlab opens M file garbled solution
[the Nine Yang Manual] 2017 Fudan University Applied Statistics real problem + analysis
甲、乙机之间采用方式 1 双向串行通信,具体要求如下: (1)甲机的 k1 按键可通过串行口控制乙机的 LEDI 点亮、LED2 灭,甲机的 k2 按键控制 乙机的 LED1
(原创)制作一个采用 LCD1602 显示的电子钟,在 LCD 上显示当前的时间。显示格式为“时时:分分:秒秒”。设有 4 个功能键k1~k4,功能如下:(1)k1——进入时间修改。
[the Nine Yang Manual] 2018 Fudan University Applied Statistics real problem + analysis
强化学习基础记录
编写程序,模拟现实生活中的交通信号灯。
[the Nine Yang Manual] 2021 Fudan University Applied Statistics real problem + analysis
1. First knowledge of C language (1)
3. Input and output functions (printf, scanf, getchar and putchar)
Get started with typescript
7-14 错误票据(PTA程序设计)
关于双亲委派机制和类加载的过程
.Xmind文件如何上传金山文档共享在线编辑?
ABA问题遇到过吗,详细说以下,如何避免ABA问题
[hand tearing code] single case mode and producer / consumer mode
仿牛客技术博客项目常见问题及解答(三)
1. Preliminary exercises of C language (1)
透彻理解LRU算法——详解力扣146题及Redis中LRU缓存淘汰