fork download
copy 
  1. for _ in range(int(input())):
  2.     n = int(input())
  3.     a = list(map(int,input().split()))
  4.     op = ['NONE', 'OPERATION1', 'OPERATION2']
  5.     x,y=0,0
  6.     temp1 = [0]*n; temp2 = [0]*n
  7.     for i in range(n):
  8.         x += a[i]
  9.         if x < 0:
  10.             x = 0
  11.         if y < x:
  12.             y = x
  13.         temp1[i] = x
  14.  
  15.     x,y = 0,0
  16.     for i in range(n-1, -1, -1):
  17.         x += a[i]
  18.         if x < 0:
  19.             x = 0
  20.         if y < x:
  21.             y = x
  22.         temp2[i] = x
  23.  
  24.     max1 = [0]*n; max2 = [0]*n; pref =[0]*n; suff =[0]*n
  25.     max1[0] = a[0];max2[-1] = a[-1]; pref[0] = a[0]; suff[-1] = a[-1] 
  26.  
  27.     for i in range(1,n):
  28.         pref[i] = pref[i-1] + a[i]
  29.         max1[i] = max(max1[i-1],pref[i])
  30.  
  31.     for i in range(n-2, -1,-1):
  32.         suff[i] = suff[i+1] + a[i]
  33.         max2[i] = max(max2[i+1],suff[i])
  34.     #print(temp1, temp2, max1, max2)
  35.     ans = y ; meth = 0
  36.  
  37.     temp_ans = 0
  38.     for i in  range(n-1, 1, -1):
  39.         temp_ans = max(temp_ans, temp2[i] + max1[i-1])
  40.  
  41.     if temp_ans > ans:
  42.         ans = temp_ans
  43.         meth = 1
  44.  
  45.     temp_ans = 0
  46.     for i in  range(n-2):
  47.         temp_ans = max(temp_ans, temp1[i] + max2[i+1])
  48.     if temp_ans > ans:
  49.         ans = temp_ans
  50.         meth = 2
  51.  
  52.  
  53.  
  54.     print(str(ans)+' '+op[meth])
Runtime error #stdin #stdout #stderr 0.12s 23756KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Traceback (most recent call last):
  File "./prog.py", line 1, in <module>
EOFError: EOF when reading a line
https://ideone.com/kqMheE
language:
Python 3 (python  3.9.5)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!