Divide & Conquer Solution in JAVA (very easy to understand)


  • 0
    L
    public class Solution {
        public int maxSubArray(int[] nums) {
            return findMax(nums, 0, nums.length - 1);
        }
    
        public int findMax(int[] nums, int start, int end) {
            if (start > end) {
                return Integer.MIN_VALUE;
            }
        
            if (start == end) {
                return nums[start];
            }
        
            int mid = start + (end - start) / 2;
        
            // max subarray in left subarray
            int leftMax = findMax(nums, start, mid - 1);
        
            // max subarray in right subarray
            int rightMax = findMax(nums, mid + 1, end);
        
        
            // max subarray which includes nums[mid]
        
            // go left (nums[mid] is included in max subarray)
            int sum = nums[mid];
            int midMax = nums[mid];
            for (int i = mid - 1; i >= start; i--) {
                sum += nums[i];
                midMax = Math.max(midMax, sum);
            }
        
            // go right
            sum = midMax;
            for (int i = mid + 1; i <= end; i++) {
                sum += nums[i];
                midMax = Math.max(midMax, sum);
            }
    
            return Math.max(midMax, Math.max(leftMax, rightMax));
        }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.