#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
struct ArrayOut {
int low, high, sum;
};
ArrayOut Find_Max_Crossing_Subarray(vector<int> &A, int low, int mid, int high) {
int leftsum,sum,maxleft,rightsum,maxright;
leftsum = -100000000;
sum = 0;
for (int i = mid; i >= low; i--) {
sum += A[i];
if (sum > leftsum) {
leftsum = sum;
maxleft = i;
}
}
rightsum = -1000000000;
sum = 0;
for (int j = mid + 1; j <= high; j++) {
sum += A[j];
if (sum > rightsum) {
rightsum = sum;
maxright = j;
}
}
ArrayOut struct_temp;
struct_temp.low = maxleft;
struct_temp.high = maxright;
struct_temp.sum = leftsum + rightsum;
return struct_temp;
}
ArrayOut Find_Maximum_Subarray(vector<int> &A, int low, int high) {
int mid;
int leftsum, rightsum,leftlow,lefthigh,rightlow,righthigh,crosslow,crosshigh,crosssum;
if (high == low) {
ArrayOut X;
X.low = low;
X.high = high;
X.sum = A[low];
return X;
}
else{
mid = floor((low + high) / 2.0);
ArrayOut left = Find_Maximum_Subarray(A, low, mid);
ArrayOut right= Find_Maximum_Subarray(A, mid + 1, high);
ArrayOut cross = Find_Max_Crossing_Subarray(A, low, mid, high);
if (left.sum >= right.sum && left.sum >= cross.sum) {
return left;
}
else {
if (right.sum >= left.sum && right.sum >= cross.sum) {
return right;
}
else {
return cross;
}
}
}
}
int main() {
int n;
cin >> n;
vector <int> A(n);
vector <int> B;
for (int i = 0; i < n; i++) {
cin >> A[i];
}
ArrayOut B= Find_Maximum_Subarray(A, 0, n - 1);
cout <<B.low<<" "<<B.high<<" "<<B.sum<<endl;
system("pause");
return 0;
}(leftlow, lefthigh, leftsum) = Find_Maximum_Subarray(A, low, mid);
(rightlow, righthigh, rightsum) = Find_Maximum_Subarray(A, mid + 1, high);
(crosslow, crosshigh, crosssum) = Find_Max_Crossing_Subarray(A, low, mid, high);#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
struct ArrayOut {
int low, high, sum;
};
ArrayOut Find_Max_Crossing_Subarray(vector<int> A, int low, int mid, int high) {
int leftsum,sum,maxleft,rightsum,maxright;
leftsum = -100000000;
sum = 0;
for (int i = mid; i >= low; i--) {
sum += A[i];
if (sum > leftsum) {
leftsum = sum;
maxleft = i;
}
}
rightsum = -1000000000;
sum = 0;
for (int j = mid + 1; j <= high; j++) {
sum += A[j];
if (sum > rightsum) {
rightsum = sum;
maxright = j;
}
}
ArrayOut struct_temp;
struct_temp.low = maxleft;
struct_temp.high = maxright;
struct_temp.sum = leftsum + rightsum;
return struct_temp;
}