当前位置:网站首页>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;
}
边栏推荐
- Yugu p1012 spelling +p1019 word Solitaire (string)
- Mortal immortal cultivation pointer-1
- 使用Spacedesk实现局域网内任意设备作为电脑拓展屏
- Reinforcement learning series (I): basic principles and concepts
- 7-5 走楼梯升级版(PTA程序设计)
- 7-14 错误票据(PTA程序设计)
- 【MySQL-表结构与完整性约束的修改(ALTER)】
- 优先队列PriorityQueue (大根堆/小根堆/TopK问题)
- 杂谈0516
- 2022泰迪杯数据挖掘挑战赛C题思路及赛后总结
猜你喜欢
Strengthen basic learning records
ABA问题遇到过吗,详细说以下,如何避免ABA问题
3. Input and output functions (printf, scanf, getchar and putchar)
甲、乙机之间采用方式 1 双向串行通信,具体要求如下: (1)甲机的 k1 按键可通过串行口控制乙机的 LEDI 点亮、LED2 灭,甲机的 k2 按键控制 乙机的 LED1
1143_ SiCp learning notes_ Tree recursion
Caching mechanism of leveldb
优先队列PriorityQueue (大根堆/小根堆/TopK问题)
Strengthen basic learning records
Redis的两种持久化机制RDB和AOF的原理和优缺点
自定义RPC项目——常见问题及详解(注册中心)
随机推荐
FAQs and answers to the imitation Niuke technology blog project (I)
7-4 散列表查找(PTA程序设计)
1. First knowledge of C language (1)
Package bedding of components
甲、乙机之间采用方式 1 双向串行通信,具体要求如下: (1)甲机的 k1 按键可通过串行口控制乙机的 LEDI 点亮、LED2 灭,甲机的 k2 按键控制 乙机的 LED1
[hand tearing code] single case mode and producer / consumer mode
【VMware异常问题】问题分析&解决办法
使用Spacedesk实现局域网内任意设备作为电脑拓展屏
这次,彻底搞清楚MySQL索引
7-5 走楼梯升级版(PTA程序设计)
Why use redis
Leetcode. 3. Longest substring without repeated characters - more than 100% solution
3. Input and output functions (printf, scanf, getchar and putchar)
. How to upload XMIND files to Jinshan document sharing online editing?
附加简化版示例数据库到SqlServer数据库实例中
7-15 h0161. 求最大公约数和最小公倍数(PTA程序设计)
String abc = new String(“abc“),到底创建了几个对象
[the Nine Yang Manual] 2018 Fudan University Applied Statistics real problem + analysis
The difference between abstract classes and interfaces
【Numpy和Pytorch的数据处理】