fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.BufferedWriter;
  3. import java.io.IOException;
  4. import java.io.InputStream;
  5. import java.io.InputStreamReader;
  6. import java.io.OutputStream;
  7. import java.io.OutputStreamWriter;
  8. import java.io.PrintWriter;
  9. import java.io.Writer;
  10. import java.util.InputMismatchException;
  11.  
  12.  
  13. class TRT {
  14. static int []a;static int N;
  15. static int ans[][];
  16. 	/**
  17. 	 * @param args
  18. 	 * @throws IOException 
  19. 	 * @throws NumberFormatException 
  20. 	 */
  21. 	public static void main(String[] args) throws NumberFormatException, IOException {
  22. 		// TODO Auto-generated method stub
  23. //BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  24.  //N=Integer.parseInt(br.readLine());
  25. 		InputReader ir=new InputReader(System.in);
  26. 		//OutputWriter ow=new OutputWriter(System.out);
  27. 		N=ir.readInt();
  28.  a=new int[N];
  29. for(int i=0;i<N;i++){
  30. 	a[i]=ir.readInt();
  31. }
  32. ans=new int[N][N];
  33.  
  34. System.out.println(solve(0, a.length-1));
  35. 	}
  36. public static int solve(int p,int q){
  37. 	if(ans[p][q]!=0)
  38. 		return ans[p][q];
  39. 		int k;
  40. 		k=q-p+1;
  41. 		k=N-k+1;
  42. 		if(p==q)
  43. 			return k*a[p];
  44. 	ans[p][q]= Math.max(k*a[p]+solve(p+1, q),k*a[q]+solve(p, q-1));
  45. 	return ans[p][q];
  46. }
  47. }
  48. class InputReader {
  49.     private InputStream stream;
  50.     private byte[] buf = new byte[1024];
  51.     private int curChar;
  52.     private int numChars;
  53.     private SpaceCharFilter filter;
  54.     public InputReader(InputStream stream) {
  55.     this.stream = stream;
  56.     }
  57.     public int read() {
  58.     if (numChars == -1)
  59.     throw new InputMismatchException();
  60.     if (curChar >= numChars) {
  61.     curChar = 0;
  62.     try {
  63.     numChars = stream.read(buf);
  64.     } catch (IOException e) {
  65.     throw new InputMismatchException();
  66.     }
  67.     if (numChars <= 0)
  68.     return -1;
  69.     }
  70.     return buf[curChar++];
  71.     }
  72.     public int readInt() {
  73.     int c = read();
  74.     while (isSpaceChar(c))
  75.     c = read();
  76.     int sgn = 1;
  77.     if (c == '-') {
  78.     sgn = -1;
  79.     c = read();
  80.     }
  81.     int res = 0;
  82.     do {
  83.     if (c < '0' || c > '9')
  84.     throw new InputMismatchException();
  85.     res *= 10;
  86.     res += c - '0';
  87.     c = read();
  88.     } while (!isSpaceChar(c));
  89.     return res * sgn;
  90.     }
  91.     public String readString() {
  92.     int c = read();
  93.     while (isSpaceChar(c))
  94.     c = read();
  95.     StringBuilder res = new StringBuilder();
  96.     do {
  97.     res.appendCodePoint(c);
  98.     c = read();
  99.     } while (!isSpaceChar(c));
  100.     return res.toString();
  101.     }
  102.     public boolean isSpaceChar(int c) {
  103.     if (filter != null)
  104.     return filter.isSpaceChar(c);
  105.     return isWhitespace(c);
  106.     }
  107.     public static boolean isWhitespace(int c) {
  108.     return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  109.     }
  110.     public char readCharacter() {
  111.     int c = read();
  112.     while (isSpaceChar(c))
  113.     c = read();
  114.     return (char) c;
  115.     }
  116.     public String next() {
  117.     return readString();
  118.     }
  119.     public interface SpaceCharFilter {
  120.     public boolean isSpaceChar(int ch);
  121.     }
  122.     }
  123.     class OutputWriter {
  124.     private final PrintWriter writer;
  125.     public OutputWriter(OutputStream outputStream) {
  126.     writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  127.     }
  128.     public OutputWriter(Writer writer) {
  129.     this.writer = new PrintWriter(writer);
  130.     }
  131.     public void print(Object...objects) {
  132.     for (int i = 0; i < objects.length; i++) {
  133.     if (i != 0)
  134.     writer.print(' ');
  135.     writer.print(objects[i]);
  136.     }
  137.     }
  138.     public void printLine(Object...objects) {
  139.     print(objects);
  140.     writer.println();
  141.     }
  142.     public void close() {
  143.     writer.close();
  144.     }
  145.     }
  146.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
6
6
1
1
1
5
5
stdout
copy 
70
https://ideone.com/ppcokV
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

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!