Poj Solution 2479

http://poj.org/problem?id=2479

 import java.io.BufferedReader;
 import java.io.InputStreamReader;

 public class Main {

     int t;
     int l;
     int[] a;
     String[] s;
     int[] left;
     int[] right;
     int max = 0;

     int temp;

     public Main() throws Exception {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         t = Integer.parseInt(read.readLine());
         for (int i = 0; i < t; i++) {
             read.readLine();
             l = Integer.parseInt(read.readLine());
             a = new int[l];
             left = new int[l];
             right = new int[l];
             s = read.readLine().split(" ");
             for (int j = 0; j < l; j++) {
                 a[j] = Integer.parseInt(s[j]);
             }
             search();
             System.out.println(max);
         }
     }

     public void search() {
         temp = a[0];
         left[0] = temp;
         for (int i = 1; i < l; i++) {
             if (temp < 0) {
                 temp = 0;
             }
             temp += a[i];
             if (temp > left[i - 1]) {
                 left[i] = temp;
             } else {
                 left[i] = left[i - 1];
             }
         }
         temp = a[l - 1];
         right[0] = temp;
         for (int i = l - 2, k = 1; i >= 0; i--, k++) {
             if (temp < 0) {
                 temp = 0;
             }
             temp += a[i];
             if (temp > right[k - 1]) {
                 right[k] = temp;
             } else {
                 right[k] = right[k - 1];
             }
         }
         max = left[0] + right[l - 2];
         for (int i = 0; i < l - 1; i++) {
             if (left[i] + right[l - i - 2] > max) {
                 max = left[i] + right[l - i - 2];
             }
         }
     }

     public int getLength(int m, int n) {
         max = Integer.MIN_VALUE;
         temp = 0;
         for (int i = m; i < n; i++) {
             temp += a[i];
             if (temp > max) {
                 max = temp;
             }
             if (temp < 0) {
                 temp = 0;
             }
         }
         return max;
     }

     public static void main(String[] args) throws Exception {
         new Main();
     } 
}

											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *