-
Notifications
You must be signed in to change notification settings - Fork 0
/
Max_good_subarray_sum.cpp
74 lines (73 loc) · 1.94 KB
/
Max_good_subarray_sum.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
// class Solution {
// public:
// long long maximumSubarraySum(vector<int>& nums, int k) {
// int i,j;
// int n = nums.size();
// long long sum=0;
// int s = 0;
// int e = n-1;
// int i1=-1,i2=-1;
// vector<long long>arr;
// while(e>0){
// s=0;
// while(s<=e){
// if(abs(nums[s]-nums[e])==k){
// sum=0;
// i1=s;
// i2=e;
// for(i=i1; i<=i2; i++){
// sum+=nums[i];
// }
// arr.push_back(sum);
// // break;
// }
// s++;
// }
// e--;
// }
// // for(i=i1; i<=i2; i++){
// // sum+=nums[i];
// // }
// long long ans=0;
// if(arr.size()>0){ans = *max_element(arr.begin(),arr.end());}
// return ans;
// }
// };
class Solution {
public:
long long maximumSubarraySum(vector<int> &nums, int k) {
map<int, vector<int>> mp;
vector<long long> ps(nums.size());
ps[0] = nums[0];
for (int i = 1; i < nums.size(); i++) {
ps[i] = ps[i - 1] + nums[i];
}
long long maxsum = LONG_MIN;
bool present = false;
long long ans;
for (int i = 0; i < nums.size(); i++) {
if (mp.find(nums[i] - k) != mp.end()) {
present = true;
for (auto x : mp[nums[i] - k]) {
if (x == 0)
ans = ps[i];
else
ans = ps[i] - ps[x - 1];
maxsum = max(maxsum, ans);
}
}
if (mp.find(nums[i] + k) != mp.end()) {
present = true;
for (auto x : mp[nums[i] + k]) {
if (x == 0)
ans = ps[i];
else
ans = ps[i] - ps[x - 1];
maxsum = max(maxsum, ans);
}
}
mp[nums[i]].push_back(i);
}
return present ? maxsum : 0;
}
};