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

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

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        // for each element: what is the largest sum that can be obtained so far?
        // by either addition or keeping the current element
        // modify num semnification to largestSum
        int max = nums[0];
        for (int i=1; i<nums.length; i++) {
            nums[i] = Math.max(nums[i], nums[i-1]+nums[i]); // replace with * for largest product
            if (max < nums[i]) {
                max = nums[i];
            }
        }
        
        return max;
    }
}

#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();
    }
}