max sum path for two arrays

Tushar Roy · Tushar Roy · commit 9edf31d389b9 · 2015-12-31T15:52:48.000-06:00
diff --git a/python/array/maximumsumpathtwoarrays.py b/python/array/maximumsumpathtwoarrays.py
@@ -0,0 +1,46 @@
+# http://www.geeksforgeeks.org/maximum-sum-path-across-two-arrays/
+
+def max_sum(input1, input2):
+    max_sum = 0
+    i = 0
+    j = 0
+    sum1 = 0
+    sum2 = 0
+    while i < len(input1) and j < len(input2):
+        if input1[i] == input2[j]:
+            if sum1 > sum2:
+                max_sum += sum1 + input1[i]
+            else:
+                max_sum += sum2 + input2[j]
+            i = i + 1
+            j = j + 1
+            sum1 = 0
+            sum2 = 0
+        elif input1[i] < input2[j]:
+            sum1 += input1[i]
+            i = i + 1
+        else:
+            sum2 += input2[j]
+            j = j + 1
+
+    while i < len(input1):
+        sum1 += input1[i]
+        i = i + 1
+
+    while j < len(input2):
+        sum2 += input2[j]
+        j = j + 1
+
+    if sum1 > sum2:
+        max_sum += sum1
+    else:
+        max_sum += sum2
+
+    return max_sum
+
+if __name__ == '__main__':
+    input1 = [2, 3, 7, 10, 12, 15, 30, 34]
+    input2 = [1, 5, 7, 8, 10, 15, 16, 19]
+
+    print(max_sum(input1, input2))
+        
diff --git a/src/com/interview/array/MaximumSumPathTwoArrays.java b/src/com/interview/array/MaximumSumPathTwoArrays.java
@@ -0,0 +1,62 @@
+package com.interview.array;
+
+/**
+ * Date 12/31/2015
+ * @author Tushar Roy
+ *
+ * Given two sorted arrays such the arrays may have some common elements. Find the sum of the maximum sum
+ * path to reach from beginning of any array to end of any of the two arrays. We can switch from one array
+ * to another array only at common elements.
+ *
+ * Time complexity is O(n + m)
+ * Space complexity is O(1)
+ *
+ * http://www.geeksforgeeks.org/maximum-sum-path-across-two-arrays/
+ */
+public class MaximumSumPathTwoArrays {
+
+    public int maxSum(int input1[], int input2[]) {
+        int maxSum = 0;
+        int i = 0, j = 0;
+        int sum1 = 0;
+        int sum2 = 0;
+        while (i < input1.length && j < input2.length) {
+            if (input1[i] == input2[j]) {
+                if (sum1 > sum2) {
+                    maxSum += sum1 + input1[i];
+                } else {
+                    maxSum += sum2 + input2[j];
+                }
+                i++;
+                j++;
+                sum1 = 0;
+                sum2 = 0;
+            } else if (input1[i] < input2[j]) {
+                sum1 += input1[i++];
+            } else {
+                sum2 += input2[j++];
+            }
+        }
+        while(i < input1.length) {
+            sum1 += input1[i++];
+        }
+        while(j < input2.length) {
+            sum2 += input2[j++];
+        }
+
+        if (sum1 > sum2) {
+            maxSum += sum1;
+        } else {
+            maxSum += sum2;
+        }
+        return maxSum;
+    }
+
+    public static void main(String args[]) {
+        int input1[] = {2, 3, 7, 10, 12, 15, 30, 34};
+        int input2[] = {1, 5, 7, 8, 10, 15, 16, 19};
+
+        MaximumSumPathTwoArrays msp = new MaximumSumPathTwoArrays();
+        System.out.println(msp.maxSum(input1, input2));
+    }
+}
