codekofi
← All questions

Maximum Product Subarray

Hard1-D Dynamic Programming

The problem

Return the largest product obtainable from a contiguous run of one or more entries.

The entries may be negative or zero, and the run must not be empty.

maxProduct({2, 3, -2, 4})

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1int maxProduct(const vector<int>& nums) {
2
3 if (nums.empty()) {
4 return 0;
5 }
6
7 int n = nums.size();
8
9 int ans = nums[0];
10 int high = nums[0];
11 int low = nums[0];
12
13 for (int i = 1; i < n; i++) {
14
15 int x = nums[i - 1];
16 int a = high * x;
17 int b = low * x;
18
19 high = max(x, max(a, b));
20 low = max(x, min(a, b));
21
22 ans = max(ans, high);
23 }
24
25 return ans;
26}
1int maxProduct(const vector<int>& nums) {
2
3 if (nums.empty()) {
4 return 0;
5 }
6
7 int n = nums.size();
8
9 int ans = nums[0];
10 int high = nums[0];
11 int low = nums[0];
12
13 for (int i = 1; i < n; i++) {
14
15 int x = nums[i];
16 int a = high * x;
17 int b = low * x;
18
19 high = max(x, max(a, b));
20 low = max(x, min(a, b));
21
22 ans = min(ans, high);
23 }
24
25 return ans;
26}
1int maxProduct(const vector<int>& nums) {
2
3 if (nums.empty()) {
4 return 0;
5 }
6
7 int n = nums.size();
8
9 int ans = nums[0];
10 int high = nums[0];
11 int low = nums[0];
12
13 for (int i = 1; i < n; i++) {
14
15 int x = nums[i];
16 int a = high * x;
17 int b = low * x;
18
19 high = max(x, max(a, b));
20 low = min(x, min(a, b));
21
22 ans = max(ans, high);
23 }
24
25 return ans;
26}