• + 9 comments

    Attention ! One correction needs to be made for this wiki solution when array has negative value, max_ending_here must be initialized to 0, while max_so_far must be initialized to either Integer.MIN_VALUE or arr[0], instead of 0, in order to handle negative values for calculating max continuous subarray.

    ps. I just corrected wiki solution.

    My working solution in java:

    static void printMaxSum(int[] arr){
    
        //1) For max continuous sub array
        int max_ending_here = 0;
        int max_so_far = Integer.MIN_VALUE;
        /*OR int max_so_far = arr[0];*/
    
        for(int x : arr){
            max_ending_here = Math.max(x, max_ending_here + x);
            max_so_far = Math.max(max_so_far, max_ending_here);
        }
    
        System.out.print(max_so_far);
    
        //2) For max non-continuous sub array, order doesn't matter
        Arrays.sort(arr);
        int sum = 0;
    
        //if there is none positive value in entire array
        if(arr[arr.length-1] <= 0)
            sum = arr[arr.length - 1];
        //accumulate all positive values in entire array
        else{
            for(int x : arr){
                if(x > 0)
                    sum += x;
            }
        }
        System.out.println(" " + sum);
    }