Untitled

 avatar
unknown
plain_text
a month ago
1.3 kB
0
Indexable
public class MaxSubarray {
    public static int[] findMaxSubarray(int[] arr) {
        int maxi = Integer.MIN_VALUE; // max sum
        int lsum = 0; // local sum
        int leftboundary = -1; // Left boundary of the subarray
        int rightboundary = -1; // Right boundary of the subarray
        int temp_start = 0; // Temporary start index

        for (int i = 0; i < arr.length; i++) {
            if (lsum == 0) { // Starting a new subarray
                temp_start = i;
            }

            lsum += arr[i];

            // Update the maximum sum and boundaries
            if (lsum > maxi) {
                maxi = lsum;
                leftboundary = temp_start;
                rightboundary = i;
            }

            // Reset local sum if it becomes negative
            if (lsum < 0) {
                lsum = 0;
            }
        }

        // Return left and right boundaries of the subarray
        return new int[]{leftboundary, rightboundary};
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int[] boundaries = findMaxSubarray(arr);

        System.out.println("Left Boundary: " + boundaries[0]);
        System.out.println("Right Boundary: " + boundaries[1]);
    }
}
Editor is loading...
Leave a Comment