Saturday, July 19, 2014

Maximum Sum Path in Two Arrays


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.

 Program:



Reference:
http://www.geeksforgeeks.org/maximum-sum-path-across-two-arrays/
Posted by at

1 comment:

  1. manojJuly 19, 2014 at 11:49 PM

    public static int maximumSumPath(int[] a, int[] b){
    int s1, s2, res, i, j;
    s1 = s2 = res = 0;

    for(i=0, j=0; i b[j])
    {
    s2 = s2+b[j++];
    }else if(a[i] < b[j]){
    s1 = s1+a[i++];
    }else{
    if(s1>s2){
    res += s1+a[i++];
    j++;
    }else{
    res += s2+b[j++];
    i++;
    }
    s1=s2=0;
    }
    }

    while(i s2){
    res += s1;
    }else{
    res += s2;
    }
    return res;
    }

    ReplyDelete

Subscribe to: Post Comments (Atom)