Thursday, November 6, 2014

Facebook: Finding maximum subsequence sum

Find the maximum sub-sequence sum (similar to Kadane's Algorithm) with the constraint that two numbers in the array that form the max sum cannot be next to each other.

Warm-up: Leetcode: maximum subarray sum
http://buttercola.blogspot.com/2014/08/leetcode-maximum-subarray.html

I. If the array contains only positive numbers
A DP Solution:

dp[n]
dp[i]: is the maximal sum from 0 to element i
dp[i] = Math.max(dp[i - 2] + A[i], dp[i - 1]);

Initial state: dp[0] = A[0];
dp[1] = Math.max(A[0], A[1]);

Code (Java):
public class Solution {
    public int maxSum(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        if (A.length == 1) {
            return A[0];
        }
        
        int[] dp = new int[A.length];
        dp[0] = A[0];
        dp[1] = Math.max(A[0], A[1]);
        
        for (int i = 2; i < A.length; i++) {
            dp[i] = Math.max(dp[i - 2] + A[i], dp[i - 1]);
        }
        
        return dp[A.length - 1];
    }

    public static void main(String[] args) {
      Solution sol = new Solution();

      int[] A = new int[]{1, 3 ,5 ,7, 9};
      int result = sol.maxSum(A);

      System.out.println("Result is " + result);
    }
}

II. What if the input array contains negative numbers
public class Solution {
    public int maxSum(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        if (A.length == 1) {
            return A[0];
        }
        
        int[] dp = new int[A.length];
        dp[0] = A[0] > 0 ? A[0] : 0;
        dp[1] = Math.max(dp[0], A[1]);
        
        for (int i = 2; i < A.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + A[i]);
        }
        
        if (dp[A.length - 1] == 0) {
            return findMax(A);
        } else {
            return dp[A.length - 1];
        }
    }
    
    private int findMax(int[] A) {
        int max = A[0];
        
        for (int i = 1; i < A.length; i++) {
            if (A[i] > max) {
                max = A[i];
            }
        }
        
        return max;
    }

    public static void main(String[] args) {
      Solution sol = new Solution();

      int[] A = new int[]{-1, -3 ,5 , 7};
      int result = sol.maxSum(A);

      System.out.println("Result is " + result);
    }
}

No comments:

Post a Comment