Pagini recente » Cod sursa (job #1646202) | Cod sursa (job #1448446) | Cod sursa (job #374529) | Cod sursa (job #137507) | Cod sursa (job #2322827)
#include "pch.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using std::cin;
using std::cout;
using std::ifstream;
using std::ofstream;
using std::vector;
using std::max;
int l = 0, r = 0;
int divide(vector<int> v, int left, int right) {
if (left == right) return max(0, v[left]);
int mid = (left + right) / 2;
int s_left = 0, s_right = 0, s = 0;
int r1 = divide(v, left, mid);
int r2 = divide(v, mid + 1, right);
for (int i = mid; i >= left; i--) {
s += v[i];
if (s_left < s) {
s_left = s;
l = i;
cout << "l = " << l << " (" << left << ", " << right << ")\n";
}
}
s = 0;
for (int i = mid + 1; i <= right; i++) {
s += v[i];
if (s_right < s) {
s_right = s;
r = i;
}
}
int r3 = s_left + s_right;
return max<int>(r1, max<int>(r2, r3));
}
int main(){
ifstream in("ssm.in");
ofstream out("ssm.out");
vector<int> v;
int x;
while (in >> x) {
v.push_back(x);
}
out << divide(v, 0, v.size() - 1);
out << l << " " << r;
}