-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtemp.c++
66 lines (53 loc) · 2.27 KB
/
temp.c++
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
#include <bits/stdc++.h>
using namespace std;
long long maxSubSumKConcat(int *arr, int n, int k)
{
vector<int>CONCAT;
for(int i = 0; i < (n*k); i++){
CONCAT.push_back(arr[i%n]);
}
long int maxSum = -2147483647;
int currSum = 0;
for(int i = 0; i < (n*k); i++){
currSum += CONCAT[i];
if(maxSum < currSum){
maxSum = currSum;
}
if(currSum < 0 && maxSum){
currSum = 0;
}
}
if(maxSum <= 0){
for(int i = 0; i < (n*k); i++){
currSum += CONCAT[i];
if(maxSum < currSum){
maxSum = currSum;
}
}
}
return maxSum;
}
int main()
{
int arr[17] = {341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625};
int n = 17;
int k = 16;
cout << maxSubSumKConcat(arr, n, k) << endl;
};
// 70118
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625
// 341, 74,-37, 608, -262, 286, 955, -506, 580, 630, 238, 222, 975, 624, 596, 305, -625