MichaelIsaakidis
BAN USERMove along each path by comparing the values at each point. Increment the path with the lowest value and add the value to the path's sum.
When you reach an intersection point, compare the sums of the paths up to this point and add the largest sum to the total sum.
#include<iostream>
#include<string>
using namespace std;
int MaxSumPath(int a[], int b[], int l1, int l2)
{
int i = 0;
int j = 0;
int totalSum = 0;
int sumA = 0;
int sumB = 0;
while(i< l1 && j < l2)
{
// If points are equal ,at intersection, add biggest sum
if(a[i] == b[j])
{
if(sumA > sumB)
{
sumA += a[i];
totalSum += sumA;
}
else
{
sumB += b[j];
totalSum += sumB;
}
sumA = 0;
sumB = 0;
i++;
j++;
}
// Else we must move on the paths
else
{
// Check which element is bigger
// Then increment the position of the smaller value
if(a[i] < b[j])
{
sumA += a[i];
i++;
}
else
{
sumB += b[j];
j++;
}
}
}
// Loop may finish without adding all elements in the list
// This will occur when the last point is not one of interception
// We therefore need to add these points to the path sums
while(i < l1)
{
sumA += a[i];
i++;
}
while(j < l2)
{
sumB += b[j];
j++;
}
// Need to add the leftover sums
if(sumA > sumB)
{
totalSum += sumA;
}
else
{
totalSum += sumB;
}
return totalSum;
}
int main()
{
int arr1[] = {3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62};
int arr2[] = {1, 4, 7, 11, 14, 25, 44, 47, 55, 57,100};
int sum = MaxSumPath(arr1,arr2,13,11);
cout<< "answer = " << sum << endl;
return 0;
}
Have two iterators, one positioned at the start,i, the other positioned at the end of the array, j.
Increment i and check if the element is zero. If the element is zero swap with element in position j and increment the counter. Decrease iterator j and continue until i==j.
The answer is obtained by subtracting the counter from the length of the array.
- MichaelIsaakidis July 02, 2014