Untitled
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