50 DSA-Questions: #5, #6, #7

#5. Maximum Subarray
Given an integer array nums, find the subarray with the largest sum, and return its sum.

public class Exercise5 {
    // private final int[] ARRAY = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; // largest subarray sum is 6; [4,-1,2,1]
    private final int[] ARRAY = {5, -9, 1, -2, 8, 0, 4}; // largest subarray sum is 12; [8,0,4]

    private void solve() {
        if (ARRAY.length == 0) {
            System.out.println("N/A");
            return;
        }

        if (ARRAY.length == 1) {
            System.out.println(ARRAY[0]);
            return;
        }

        // for each element: what is the largest sum that can be obtained so far?
        // by either addition or keeping the current element
        Integer[] largestSum = new Integer[ARRAY.length];
        largestSum[0] = ARRAY[0];
        for (int i=1; i<ARRAY.length; i++) {
            largestSum[i] = Math.max(ARRAY[i], largestSum[i-1]+ARRAY[i]); // replace with * for largest product
        }

        int max = largestSum[0];
        for (int i=1; i<largestSum.length; i++) {
            if (max < largestSum[i]) {
                max = largestSum[i];
            }
        }
        System.out.println("Largest sum = " + max);
    }

    public static void main(String args[]) {
        new Exercise5().solve();
    }
}

#6. La fel ca #5, dar se cere produsul.

#7. Find the Minimum in Rotated Sorted Array

Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log n) time.

public class Exercise7 {
    private final int[] ARRAY = {3,4,5,1,2}; // min = 1
    // private final int[] ARRAY = {10,12,0,4,5,7}; // min = 0
    // private final int[] ARRAY = {5,7,8,9,10}; // min = 5
    // private final int[] ARRAY = {3,4,6,7,8,9,2}; // min = 2

    private void find(int leftIndex, int rightIndex) {
        if (leftIndex == rightIndex || leftIndex + 1 == rightIndex) { // one or two elements left
            System.out.println("Min = " + Math.min(ARRAY[leftIndex], ARRAY[rightIndex]));
            return;
        }

        int mid = leftIndex + (rightIndex - leftIndex) / 2;
        if (ARRAY[leftIndex] <= ARRAY[mid] && ARRAY[mid] <= ARRAY[rightIndex]) { // sorted array
            System.out.println("Min = " + ARRAY[leftIndex]);
            return;
        }

        if (ARRAY[leftIndex] > ARRAY[mid]) { // search in left array
            find(leftIndex, mid);
            return;
        }

        find(mid+1, rightIndex); // search in right array
    }

    private void solve() {
        find(0, ARRAY.length - 1);
    }

    public static void main(String args[]) {
        new Exercise7().solve();
    }
}