fork download
copy 
  1.  
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. class Ideone {
  8.     public static void main (String[] args) throws java.lang.Exception {
  9.         Scanner sc=new Scanner(System.in);
  10.         int n=sc.nextInt();
  11.         int arr[]=new int[n];
  12.         for(int i=0;i<n;i++){
  13.             arr[i]=sc.nextInt();
  14.         }
  15.  
  16.  
  17.         // brute force 
  18.  
  19.  
  20. //         int ans=Integer.MIN_VALUE;
  21. //         for(int k=1;k<n;k++){
  22. //             int num1=maxSum(0,k-1,arr);
  23. //             int num2=maxSum(k,n-1,arr);
  24. //             ans=Math.max(ans,num1+num2);
  25. //         }
  26. //         System.out.print(ans);
  27. //     }
  28.  
  29. //     public static int maxSum(int p,int q,int arr[]){
  30. //         int maxArray=Integer.MIN_VALUE;
  31. //         int sum=0;
  32. //         for(int i=p;i<=q;i++){
  33. //             sum += arr[i];
  34. //             if(sum>maxArray){
  35. //                 maxArray=sum;
  36. //             }
  37. //             if(sum<0){
  38. //                 sum=0;
  39. //             }
  40. //         }
  41. //         return maxArray;
  42. //     }
  43. // }
  44.  
  45.  
  46. //OPTIMIZE VERSION
  47.  
  48.          int pfMax[]=new int[n];
  49.         int sfMax[]=new int[n];
  50.  
  51.         int sum=0;
  52.         int prMaxSum=0;
  53.  
  54.         for(int i=0;i<n;i++){
  55.             sum += arr[i];
  56.             prMaxSum = Math.max(prMaxSum, sum);
  57.             if(sum < 0) sum = 0;
  58.             pfMax[i]=prMaxSum;
  59.         }
  60.  
  61.         sum=0;
  62.         int sfMaxSum=0;
  63.         for(int i=n-1;i>=0;i--){
  64.             sum += arr[i];
  65.             sfMaxSum = Math.max(sfMaxSum, sum);
  66.             if(sum < 0) sum = 0;
  67.             sfMax[i]=sfMaxSum;
  68.         }
  69.  
  70.         int ans=0;
  71.         for(int i=1;i<n;i++){
  72.             int combined = pfMax[i-1] + sfMax[i];
  73.             ans = Math.max(ans, combined);
  74.         }
  75.  
  76.         System.out.print(ans);
  77.  
  78.  
  79.  
  80.     }
  81. }
  82.  
Success #stdin #stdout 0.14s 56656KB
comments (?)
stdin
copy 
7
2
5
-1
2
-10
1
5
stdout
copy 
14
https://ideone.com/LCAD11
language:
Java (HotSpot 12)
created:
6 days 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!