Clean Java O(n) solution
I tried dfs with memo first but realized at the end that this can be solved using a simple linear solution. \n\nWe can think that the two arrays are divided by 
I tried dfs with memo first but realized at the end that this can be solved using a simple linear solution. \n\nWe can think that the two arrays are divided by their common elements (assume 0 and Integer.MAX_VALUE are also in both the arrays). Since we can swap to another array only if we see a common element then we can simply calculate the sum from last common element and choose the max of the two sum.\n\n```\nclass Solution {\n    \n    private static long MOD = 1_000_000_007;\n    \n    public int maxSum(int[] nums1, int[] nums2) {\n        int m = nums1.length, n = nums2.length, i = 0, j = 0;\n        long res = 0, sum1 = 0, sum2 = 0;\n        while(i < m || j < n){\n            int v1 = i == m ? Integer.MAX_VALUE : nums1[i];\n            int v2 = j == n ? Integer.MAX_VALUE : nums2[j];\n            if(v1 == v2){\n                res += Math.max(sum1, sum2);\n                i++;\n                j++;\n                sum1 = sum2 = v1;\n            }else if(v1 < v2){\n                sum1 += v1;\n                i++;\n            }else{\n                sum2 += v2;\n                j++;\n            }\n        }\n        res += Math.max(sum1, sum2);\n        return (int)(res % MOD);\n    }\n}\n```
[]