Question

How to find contiguous subarray with the largest sum in Java

Answer 1

import java.util.Arrays;

public class MyClass {
    public static int[] max_subarray(int[] arr) {
        if (arr.length <= 1) {
            return arr;
        }
 
        int maximum_sum_of_subarray = Integer.MIN_VALUE;
        int maximum_sum_at_current_index = 0;
        int start = 0, end = 0;
        int star_index_of_positive_sum_sequence = 0;
 
        for (int i = 0; i < arr.length; i++) {
            maximum_sum_at_current_index += arr[i];
 
            if (maximum_sum_at_current_index < arr[i]) {
                maximum_sum_at_current_index = arr[i];
                star_index_of_positive_sum_sequence = i;
            }
 
            if (maximum_sum_of_subarray < maximum_sum_at_current_index) {
                maximum_sum_of_subarray = maximum_sum_at_current_index;
                start = star_index_of_positive_sum_sequence;
                end = i;
            }
        }
 
        return Arrays.copyOfRange(arr, start, end + 1);
    }
    public static void main(String args[]) {
        int arr[] = { -3, 2, -4, 3, 5, -2, 4, 3, -6, 5 }; //  3 + 5 + -2 + 4 + 3 = 13
 
        int subarray[] = max_subarray(arr);
        
        System.out.print(Arrays.toString(subarray));
    }
}



/*
run:

[3, 5, -2, 4, 3]

*/

 

70+ SQL courses for beginners and professionals