fork download
copy 
  1. import java.io.IOException;
  2. import java.io.InputStream;
  3. import java.io.OutputStream;
  4. import java.io.PrintWriter;
  5. import java.util.HashMap;
  6. import java.util.InputMismatchException;
  7. import java.util.Scanner;
  8.  
  9.  
  10. public class Main {
  11. 	public static void main(String[] args){
  12. 		new Main().run();
  13. 	}
  14.  
  15. 	int n;
  16. 	long[] arr;
  17.  
  18. 	public void run(){
  19.  
  20. 		Scanner sc = new Scanner(System.in);
  21. 		int n = sc.nextInt();
  22.  
  23. 		int[] arr = new int[n];
  24. 		for(int i=0; i<n; i++){
  25. 			arr[i] = sc.nextInt();
  26. 		}
  27.  
  28. 		int lo = 0;
  29. 		int hi = 1;
  30. 		int sum = arr[0] + arr[1];
  31. 		int index = 0;
  32. 		int prefixSum = arr[0];
  33.  
  34. 		int bestSum = sum;
  35. 		int bestLo = 0;
  36. 		int bestHi = 1;
  37.  
  38. 		while(true){
  39. 			// Removes bad prefixes that sum to a negative value. 
  40. 			while(true){
  41. 				if(hi-index <= 1){
  42. 					break;
  43. 				}
  44. 				if(prefixSum<0){
  45. 					sum -= prefixSum;
  46. 					lo = index+1;
  47. 					index++;
  48. 					prefixSum = arr[index];
  49. 					break;
  50. 				}else{
  51. 					prefixSum += arr[++index];
  52. 				}
  53. 			}
  54.  
  55. 			if(sum > bestSum){
  56. 				bestSum = sum;
  57. 				bestLo = lo;
  58. 				bestHi = hi;
  59. 			}
  60.  
  61. 			if(hi==arr.length-1){
  62. 				break;
  63. 			}
  64.  
  65. 			sum += arr[++hi];
  66. 		}
  67. 		System.out.println("ANS : " + bestSum);
  68. 		System.out.println("Interval : " + bestLo + " to " + bestHi);
  69. 	}
  70.  
  71. }
Success #stdin #stdout 0.13s 321088KB
comments (?)
stdin
copy 
9
-2 3 4 -5 9 -13 100 -101 7
stdout
copy 
ANS : 98
Interval : 1 to 6
https://ideone.com/dkhpa0
language:
Java (HotSpot 12)
created:
9 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!