fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. class MaxSumSubArray {
  4.  
  5. public static void main(String[] args) {
  6.  
  7. 		Scanner sc = new Scanner(System.in);
  8. 		int numOfTestCase = sc.nextInt();
  9.  
  10. 		for (int i=0;i<numOfTestCase;i++) {
  11. 			int arrSize = sc.nextInt();
  12. 			int arr[] = new int[arrSize];
  13. 			for (int j=0;j<arrSize;j++) {
  14. 				arr[j] = sc.nextInt();
  15. 			}
  16. 			System.out.print(findMaxContSubArray(arr) + " ");
  17. 			System.out.println(maxsumNonContiguous(arr));
  18. 		}
  19. 		sc.close();
  20. 	}
  21.  
  22.  
  23.  
  24.  
  25.   public static int findMaxContSubArray(int[] arr){
  26.  
  27. 	  if (checkAllNegative(arr)) {
  28. 	    	 int max = findMax(arr);
  29. 	    	 return max;
  30.      	}
  31.  
  32. 	  int max_so_far = 0, max_ending_here = 0;
  33.  
  34. 	    for (int i = 0; i < arr.length; i++)
  35. 	    {
  36. 	        max_ending_here = max_ending_here + arr[i];
  37. 	        if (max_ending_here < 0)
  38. 	            max_ending_here = 0;
  39. 	        if (max_so_far < max_ending_here)
  40. 	            max_so_far = max_ending_here;
  41. 	    }
  42. 	    return max_so_far;
  43.   }
  44.  
  45.   public static int maxsumNonContiguous(int[] arr){
  46. 	     if(arr == null)
  47. 	        return 0;
  48.  
  49. 	     if (checkAllNegative(arr)) {
  50. 	    	 int max = findMax(arr);
  51. 	    	 return max;
  52. 	     }
  53.  
  54. 	     int arrayLength = arr.length;
  55. 	     int sum1 = arr[0];
  56. 	     int sum2 = 0;
  57. 	     int sum3 =0;
  58. 	     for(int i = 1; i  <  arrayLength; i++){
  59. 	         sum3 = Math.max(sum1,sum2);
  60. 	         sum2 = sum3;
  61. 	         sum1 = sum2 + arr[i];
  62. 	     }
  63. 	     return Math.max(sum1, sum2);
  64. 	 }
  65.  
  66.   public static boolean checkAllNegative(int arr[]) {
  67. 	  for (int i=0;i<arr.length;i++) {
  68. 		  if (arr[i] >= 0)
  69. 			  return false;
  70. 	  }
  71. 	  return true;
  72.   }
  73.  
  74.   public static int findMax(int arr[]) {
  75. 	  int max=Integer.MIN_VALUE;
  76. 	  for (int i=0;i<arr.length;i++) {
  77. 		  if (arr[i] > max) {
  78. 			  max = arr[i];
  79. 		  }
  80. 	  }
  81. 	  return max;
  82.   }
  83.  
  84. }
  85.  
Success #stdin #stdout 0.06s 711680KB
comments (?)
stdin
copy 
1
4
1 2 3 4
stdout
copy 
10 10
https://ideone.com/XKz309
language:
Java (HotSpot 12)
created:
8 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!