1235. Maximum Profit in Job Scheduling

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

 

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

 

Constraints:

• 1 <= startTime.length == endTime.length == profit.length <= 5 * 104
• 1 <= startTime[i] < endTime[i] <= 109
• 1 <= profit[i] <= 104

My answer: basically, it is sorting by end time, and look for the nearest job which is compatible with current job via BS, and find if including or excluding current job can produce max profit at ith element.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

class Solution { class Job { public int start; public int end; public int profit; public Job(int start, int end, int profit) { this.start = start; this.end = end; this.profit = profit; } } public int jobScheduling(int[] startTime, int[] endTime, int[] profit) { if (profit == null) { return 0; } if (profit.length == 1) { return profit[0]; } List<Job> jobs = new ArrayList<Job>(); for (int i = 0; i < profit.length; i ++) { jobs.add(new Job(startTime[i], endTime[i], profit[i])); } Collections.sort(jobs, (a, b) -> Integer.compare(a.end, b.end)); // dp is max profit from 0 to ith element // only 2 choices: including ith or excluding ith // if including ith, look for nearest compatible job plus ith value // if excluding ith, use dp[i - 1] int[] dp = new int[jobs.size()]; dp[0] = jobs.get(0).profit; for (int i = 1; i < jobs.size(); i ++) { dp[i] = jobs.get(i).profit; int j = bs(jobs, 0, i, jobs.get(i)); if (j == -1) { dp[i] = Math.max(dp[i - 1], jobs.get(i).profit); } else { dp[i] = Math.max(dp[i - 1], dp[j] + jobs.get(i).profit); } } return dp[jobs.size() - 1]; } // find the rightmost job which can be scheduled before target private int bs(List<Job> jobs, int l, int r, Job target) { while(l < r) { int m = (l + r)/2; Job mid = jobs.get(m); if (mid.end <= target.start) { l = m + 1; } else { r = m; } } return (l - 1); } private int helper(int currentIndex, List<Job> jobs, List<Job> selectedJobs) { if (currentIndex == jobs.size()) { int profitSum = 0; for (Job job : selectedJobs) { profitSum += job.profit; } return profitSum; } int max = 0; if (canFit(selectedJobs.get(selectedJobs.size() - 1), jobs.get(currentIndex))) { selectedJobs.add(jobs.get(currentIndex)); max = helper(currentIndex + 1, jobs, selectedJobs); // back track selectedJobs.remove(selectedJobs.size() - 1); max = Math.max(max, helper(currentIndex + 1, jobs, selectedJobs)); } else { // cannot fit max = helper(currentIndex + 1, jobs, selectedJobs); } return max; } private boolean canFit(Job lastJob, Job currentJob) { return lastJob.end <= currentJob.start; } }

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [0]
Output: 0

Example 4:

Input: nums = [-1]
Output: -1

Example 5:

Input: nums = [-100000]
Output: -100000

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -105 <= nums[i] <= 105

 

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. 

My answer:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

public class Solution { public int maxSubArray(int[] nums) { // answer before 2021 // int globalMax = nums[0]; // int localMax = nums[0]; // for (int i = 1; i < nums.length; i ++) { // // localMax is the bigger value which includes "i"th number, so that the globalMax can be the result of contiguous subarray // localMax = Math.max(nums[i], localMax + nums[i]); // globalMax = Math.max(globalMax, localMax); // } // return globalMax; // answer on 2021 if (nums == null || nums.length == 0) { return 0; } if (nums.length == 1) { return nums[0]; } // dp is the value where max sum given i th element must be included int[] dp = new int[nums.length]; dp[0] = nums[0]; for (int i = 1; i < nums.length; i ++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); } int maxSum = dp[0]; for (int i = 1; i < dp.length; i ++) { maxSum = Math.max(maxSum, dp[i]); } return maxSum; } }

Regarding the follow up via Divide and Conqure: below answer is from Leetcode forum. 

Divide and Conquer

The Divide-and-Conquer algorithm breaks nums into two halves and find the maximum subarray sum in them recursively. Well, the most tricky part is to handle the case that the maximum subarray spans the two halves. For this case, we use a linear algorithm: starting from the middle element and move to both ends (left and right ends), record the maximum sum we have seen. In this case, the maximum sum is finally equal to the middle element plus the maximum sum of moving leftwards and the maximum sum of moving rightwards.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return maxSubArray(nums, 0, nums.size() - 1);
    }
private:
    int maxSubArray(vector<int>& nums, int l, int r) {
        if (l > r) {
            return INT_MIN;
        }
        int m = l + (r - l) / 2, ml = 0, mr = 0;
        int lmax = maxSubArray(nums, l, m - 1);
        int rmax = maxSubArray(nums, m + 1, r);
        for (int i = m - 1, sum = 0; i >= l; i--) {
            sum += nums[i];
            ml = max(sum, ml);
        }
        for (int i = m + 1, sum = 0; i <= r; i++) {
            sum += nums[i];
            mr = max(sum, mr);
        }
        return max(max(lmax, rmax), ml + mr + nums[m]);
    

152. Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0 

Explanation: The result cannot be 2, because [-2,-1] is not a subarray. 

My answer:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

public class Solution { public int maxProduct(int[] A) { //Previous answer // if (A.length == 0) { // return 0; // } // int maxherepre = A[0]; // int minherepre = A[0]; // int maxsofar = A[0]; // int maxhere, minhere; // for (int i = 1; i < A.length; i++) { // maxhere = Math.max(Math.max(maxherepre * A[i], minherepre * A[i]), A[i]); // minhere = Math.min(Math.min(maxherepre * A[i], minherepre * A[i]), A[i]); // maxsofar = Math.max(maxhere, maxsofar); // maxherepre = maxhere; // minherepre = minhere; // } // return maxsofar; // current answer if (A.length == 0) { return 0; } if (A.length == 1) { return A[0]; } // dp[i][0] is the max value of product with ith elment included // dp[i][1] is the min value of product with ith elment included int[][] dp = new int[A.length][2]; dp[0][0] = A[0]; dp[0][1] = A[0]; for (int i = 1; i < A.length; i++) { // max product can only come from dp[i].min * A[i], dp[i].max * A[i], A[i] dp[i][0] = Math.max(A[i], Math.max(dp[i-1][0] * A[i], dp[i-1][1] * A[i])); dp[i][1] = Math.min(A[i], Math.min(dp[i-1][0] * A[i], dp[i-1][1] * A[i])); } int result = Integer.MIN_VALUE; for (int i = 0; i < dp.length; i ++) { result = Math.max(result, dp[i][0]); } return result; } }

474. Ones and Zeroes

 You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

 

Example 1:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

Example 2:

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.

 

Constraints:

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] consists only of digits '0' and '1'.
• 1 <= m, n <= 100

Answer:

class Solution {
    /**
    *To better understand, DP[][] can be rewrite as DP[][][], 
    *e.g. DP[0][i][j] = 0 means when the string array is empty, 
    *we can not form any string. Then we put the first element of strs in our pool,
    *and we can write DP[1][i][j]=Math.max(DP[0][i][j], 1+DP[0][i-c[0]][j-c[1]]);
    *(for each i and j). Actually, we find that each time we add one more string k,
    *DP[k][i][j]=Math.max(DP[k-1][i][j], 1+DP[k-1][i-c[0]][j-c[1]]). 
    *Since each i and j will not be influenced by higher i,j, 
    * and DP[k-1] will not be used in the future, 
    * we can iterate backward and update DP[i][j] in place. 
    * In the end, we return DP[m][n] which is actually DP[strs.length][m][n].
    *
    **/
    public int findMaxForm(String[] strs, int m, int n) {
        if(strs.length==0) return 0;
        int[][] DP=new int[m+1][n+1];
        for(String str:strs){
            int[] c=count(str);
            for(int i=m;i>=c[0];i--){
                for(int j=n;j>=c[1];j--){
                    DP[i][j]=Math.max(DP[i][j], 1+DP[i-c[0]][j-c[1]]);
                }
            }
        }
        return DP[m][n];

    }
    int[] count(String str){
        int[] c=new int[2];
        for(int i=0;i<str.length();i++){
            c[str.charAt(i)-'0']++;
        }
        return c;
    }
}

My Summary: the key points here are: 

1. since there could be multiple combinations as result meeting requirements, the best solution is very likely to be using DP

2. DP solution's key point is to figure out the X/Y Axis, and the relation between DP[X(k)i][X(k)j] and DP[X(k+1)i][X(k+1)j], Xk and X(k+1) is element in original array and its following element.

[2018-Interview] Longest Palindromic Substring

Original question: https://leetcode.com/problems/longest-palindromic-substring/description/

My answer:

Used answer from Jiuzhang as reference:

https://www.jiuzhang.com/solutions/longest-palindromic-substring/

Answer 1: DP solution

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i ++) {
            isPalindrome[i][i] = true;
        }

        int maxLength = 1;
        int start = 0;
        
        for (int i = n - 2; i >= 0; i --) {
            isPalindrome[i][i + 1] = s.charAt(i) == s.charAt( i + 1);
            if (isPalindrome[i][i + 1] ) {
                start = i;
                maxLength = 2;
            }
        }

        for (int i = n - 1; i >= 0; i --) {// start from end; 
            // otherwise, if start from beginning, there won't be [i+1][j-1] for reference
            for (int j = i + 2; j < n; j ++) {
                isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && (s.charAt(i) == s.charAt(j));
                if (isPalindrome[i][j]) {
                    if (j - i + 1 > maxLength) {
                        maxLength = j - i + 1;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start, start + maxLength);
    }
}

Answer 2: try to find the longest palindrome with each point as center point

/**
* 本参考程序来自九章算法，由 @令狐冲 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        int start = 0, len = 0, longest = 0;
        for (int i = 0; i < s.length(); i++) {
            len = findLongestPalindromeFrom(s, i, i);
            if (len > longest) {
                longest = len;
                start = i - len / 2;
            }
            
            len = findLongestPalindromeFrom(s, i, i + 1);
            if (len > longest) {
                longest = len;
                start = i - len / 2 + 1;
            }
        }
        
        return s.substring(start, start + longest);
    }
    
    private int findLongestPalindromeFrom(String s, int left, int right) {
        int len = 0;
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            len += left == right ? 1 : 2;
            left--;
            right++;
        }
        
        return len;
    }
}