/
max product subarray.cpp
142 lines (94 loc) · 2.65 KB
/
max product subarray.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
/*
//////////////////////////////////////////////////////
//Question/Info
152. Maximum Product Subarray
Medium
7407
239
Add to List
Share
Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
It is guaranteed that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
----------------------GFG-----------------------
Maximum Product Subarray
Medium Accuracy: 29.84% Submissions: 56307 Points: 4
Given an array Arr that contains N integers (may be positive, negative or zero). Find the product of the maximum product subarray.
Example 1:
Input:
N = 5
Arr[] = {6, -3, -10, 0, 2}
Output: 180
Explanation: Subarray with maximum product
is 6, -3, -10 which gives product as 180.
Example 2:
Input:
N = 6
Arr[] = {2, 3, 4, 5, -1, 0}
Output: 120
Explanation: Subarray with maximum product
is 2, 3, 4, 5 which gives product as 120.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxProduct() which takes the array of integers arr and n as parameters and returns an integer denoting the answer.
Note: Use 64-bit integer data type to avoid overflow.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 500
-102 ≤ Arri ≤ 102
Company Tags
Amazon D-E-Shaw Microsoft Morgan Stanley OYO Rooms Google
author: srj_v
//////////////////////////////////////////////////////
*/
#include <bits/stdc++.h>
using namespace std;
#define _IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long double ld;
typedef long long int lli;
#pragma GCC optimize("Ofast")
void c_p_c()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
//////////////////////////////////////////////////////
int32_t main() {
///////////
// c_p_c();
///////////
_IOS
//////////
// code
/*
int t ; cin >> t; while(t--){}
*/
class Solution {
public:
int maxProduct(vector<int>& nums) {
if (nums.size() == 1) return nums[0];
int n = nums.size();
int mins = 0, maxs = 0, ans = INT_MIN;
for (int i = 0 ; i < n; i++) {
if (nums[i] < 0) swap(mins, maxs);
maxs = max(maxs * nums[i], nums[i]);
mins = min(mins * nums[i], nums[i]);
ans = max(ans, maxs);
}
return ans;
}
};
// cerr << "time: " << clock() << " ms" << '\n';
return 0;
}
//////////////////////////////////////////////////////