[Java] O(n) Time, O(1) space beat 100% cpu+memory. Explained.
The idea is same as DP:\n\nthe max sum of the full path = the max sum of elements from the beginning to the next common element + the max sum of remaining subpa
The idea is same as DP:\n\n`the max sum of the full path` = `the max sum of elements from the beginning to the next common element` + `the max sum of remaining subpaths`\n\nBecause no matter which path leads to the common element `C`, from `C`  we can go ahead following any paths to the end, then just need to choose the max path to `C` first.\n\nIn order to do that we need 2 pointers `i`, `j` and 2 sums `sum1`, `sum2`.\n\nUse `i`, `j` to traverse 2 arrays from left to right and find the common element `C`. While traversing calculate the sum for each array: `sum1` is sum of elements of array `nums1` from the begining to the `C`. The same for `sum2` and `nums2`. We only need 2 sums because from `C1` to the next `C2` there are only 2 direct subpaths on each arrays.\n\nAt the common element `C` we set `sum1` = `sum2` = `the max sum of elements from the beginning to C` cause it doesn\'t matter which path led to `C`\n\n\n```\n    public int maxSum(int[] nums1, int[] nums2) {\n      long sum1 = 0, sum2 = 0;\n      int i = 0, j = 0;\n      while (i < nums1.length && j < nums2.length) {\n        if (nums1[i] < nums2[j]) {\n          sum1 += nums1[i++];\n        } else if (nums2[j] < nums1[i]) {\n          sum2 += nums2[j++];\n        } else {\n          sum1 = Math.max(sum1, sum2) + nums1[i];\n          sum2 = sum1;\n          i++;\n          j++;\n        }\n      }\n\n      while (j < nums2.length) sum2 += nums2[j++];\n      while (i < nums1.length) sum1 += nums1[i++];\n\n      return (int) (Math.max(sum1, sum2) % 1000000007);\n    }\n```\n\nComplextiy: O(n)\nSpace Complexity: O(1)
['Two Pointers', 'Java']