FilesExpand file tree

 master

/

MaximumSumPathTwoArrays.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

62 lines (57 loc) · 1.73 KB

 master

/

MaximumSumPathTwoArrays.java

Copy path

Top

File metadata and controls

• Code
• Blame

62 lines (57 loc) · 1.73 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

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));

}

}