-
Notifications
You must be signed in to change notification settings - Fork 0
/
maxSubArray.cpp
62 lines (44 loc) · 1.41 KB
/
maxSubArray.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
// You are asked to write a function called max_slice which takes as an input an array of integers, and returns the slice with the largest sum of the elements.
// 8, -7, 3, 2, 5 -> return whole array
//
#include <iostream>
#include <utility>
#include <vector>
#include <climits>
using namespace std;
// To execute C++, please define "int main()"
vector<int> findLargestSlice(const vector<int> & v) {
vector<int> output, result;
int bestSumSoFar = 0;
int maxEndingHere = 0;
for (unsigned int i = 0; i <v.size(); ++i) {
maxEndingHere = maxEndingHere + v[i];
output.push_back(v[i]);
if (maxEndingHere < 0) {
maxEndingHere = 0;
output.clear();
}
if (maxEndingHere > bestSumSoFar) {
bestSumSoFar = maxEndingHere;
result.clear();
copy(output.begin(), output.end(), std::back_inserter(result)); //check on vector copy
}
}
return result;
}
int main() {
std::vector<int> v = {-1,-9};
//vector<int> v = { -1, -2 , 1 , 2};
//vector<int> v = {-8, -7, -5};
//vector<int> v = {8,-7,-3,-2,-5};
// vector<int> v = {8,-7,3,2,5};
// vector<int> v = {8,-9,3,2,5};
// vector<int> v = {8,7,3,2,5};
vector<int> output = findLargestSlice(v);
for (unsigned int i = 0; i < output.size(); i++) {
cout << output[i]<< " ";
}
cout<<endl;
cout<<"finished";
return 0;
}