Advertisement
Guest User

Untitled

a guest
Feb 26th, 2017
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.84 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. int main() {
  6. int n;
  7. cin >> n;
  8. int Array[10*1000 + 1];
  9. Array[0] = 0;
  10. for (int *q = Array + 1; q <=Array + n; q++) {
  11. cin >> *q;
  12. *q += *(q - 1);
  13. }
  14. int ans_left, ans_right, max_sum = 0;
  15. int min_left[10*1000 + 1];
  16. min_left[0] = 0;
  17. for (int i = 1; i <= n; i++) {
  18. if (Array[min_left[i - 1]] < Array[i - 1] && Array[i] > Array[min_left[i - 1]])
  19. min_left[i] = min_left[i - 1];
  20. else if (Array[i] > Array[i - 1] && Array[i - 1] <= Array[min_left[i - 1]])
  21. min_left[i] = i - 1;
  22. else
  23. min_left[i] = i;
  24. }
  25. for (int i = 1; i <= n; i++) {
  26. if (Array[i] - Array[min_left[i]] > max_sum) {
  27. max_sum = Array[i] - Array[min_left[i]];
  28. ans_left = min_left[i] + 1;
  29. ans_right = i;
  30. }
  31. }
  32. cout << ans_left << " " << ans_right;
  33. return 0;
  34. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement