int kadane(vector<int> const &arr) {
int max_num = *max_element(arr.begin(), arr.end());
if (max_num < 0) {
return max_num;
}
int max_so_far = 0;
int max_ending_here = 0;
for (int i = 0; i < arr.size(); i++) {
max_ending_here = max_ending_here + arr[i];
max_ending_here = max(max_ending_here, 0);
max_so_far = max(max_so_far, max_ending_here);
}
return max_so_far;
}