-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMaxSubArray.cpp
More file actions
93 lines (78 loc) · 2.63 KB
/
MaxSubArray.cpp
File metadata and controls
93 lines (78 loc) · 2.63 KB
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
#include <iostream>
#include <vector>
using namespace std;
/**
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.
*/
struct SubArray {
int begin;
int end;
int product;
SubArray(int b, int e, int p) {
begin = b;
end = e ;
product = p;
}
};
SubArray findMaxSubArray(vector<int> array) {
if(array.size() == 0) {
return SubArray(-1, -1, 0);
}
vector<SubArray> minList, maxList;
minList.reserve(array.size());
maxList.reserve(array.size());
minList[0] = SubArray(0, 0, array[0]);
maxList[0] = SubArray(0, 0, array[0]);
int maxIdx = 0;
for(size_t i = 1; i < array.size(); ++i) {
if(array[i] >= 0) {
if(array[i] > array[i] * maxList[i - 1].product) {
maxList[i] = SubArray(i, i, array[i]);
}else {
maxList[i] = SubArray(maxList[i - 1].begin, i, array[i] * maxList[i - 1].product);
}
if(array[i] < array[i] * minList[i - 1].product) {
minList[i] = SubArray(i, i, array[i]);
}else {
minList[i] = SubArray(minList[i - 1].begin, i, array[i] * minList[i - 1].product);
}
}else {
if(array[i] > array[i] * minList[i - 1].product) {
maxList[i] = SubArray(i, i, array[i]);
}else {
maxList[i] = SubArray(minList[i - 1].begin, i, array[i] * minList[i - 1].product);
}
if(array[i] < array[i] * maxList[i - 1].product) {
minList[i] = SubArray(i, i, array[i]);
}else {
minList[i] = SubArray(maxList[i - 1].begin, i, array[i] * maxList[i - 1].product);
}
}
if(maxList[maxIdx].product < maxList[i].product) {
maxIdx = i;
}
}
return maxList[maxIdx];
}
int main() {
{
int a[] = {2, 3, -2, 4};
vector<int> array(a, a+4);
SubArray result = findMaxSubArray(array);
if(result.begin != -1) {
cout << "begin:" << result.begin << " end:" << result.end << endl;
cout << "max product:" << result.product << endl;
}
}
{
int a[] = {2, 3, -2, 4, -1};
vector<int> array(a, a+5);
SubArray result = findMaxSubArray(array);
if(result.begin != -1) {
cout << "begin:" << result.begin << " end:" << result.end << endl;
cout << "max product:" << result.product << endl;
}
}
return 0;
}