C++ soln! REASON behind MODULO in the end and not at every step?
So, i also did the same mistake that most of u may have done.. Taking modulo at every step or when sum is greater than equal to 1e9+7. But OBVIOUSLY, it is fail
So, i also did the same mistake that most of u may have done.. Taking modulo at every step or when sum is greater than equal to **1e9+7**. But OBVIOUSLY, it is failing for larger test-cases. **AND IT SHOULD!**\n\n**REASON:** The reason behind this is when one of the array sum gets bigger than 1e9+7, taking modulo makes it\'s value smaller in comparision to the second array whose sum is still smaller than 1e9+7. And at intersection point or at the end when we have to take maximum, it will take the second one. \nBut, the sum of first one was greater, so *obviously* it should be taken.\n\n**For Example-** If first array *nums1* contains 10^5 elements starting from some x to 10^7 (Please ignore any mathematical error) and second array *nums2* might contains just 2 elements i.e, {10^7-1, 10^7}\n\n```\nnums1 = {x, x+1 , x+2 , , , , , , ,  ,  , 10^7} \nsize1= 10^5\nsum1 >= 10^9+7 anyways\nnums2 = {10^7-1, 10^7} \nsize2 2\nsum2 is 2*10^7-1\n```\n\nSo, now first array sum will be the answer but taking modulo at every time will make the sum shorter in comparision to the sum of second array. Hence, second array sum will be taken which will give **Wrong Answer**\n\n**Solution:** To avoid this, the maximum value than it can reach is 10^12. Taking *long long int* will solve the problem. And at the end, since we have to return 32-bit integer so take modulo and return it.\nRest, i think it\'s simple to understand how dp is working. \n**1** Taking maximum of the sums at each intersection point and at the end will give the answer. \n**2** To get that, take two pointers eah for an array and start traversing.\n**3** Check sum and take maximum at every intersection point or at the end and add it to the answer.\nThis will require 1-Pass of both the arrays.\nCode will clear any remaining doubts.\n\nMy solution takes O(N+M) time where N and M are the sizes of 2 arrays and requires O(1) space.\n\nRuntime: **240 ms**\nMemory Usage: **55.7 MB**\n\n```\nclass Solution {\npublic:\n    int maxSum(vector<int>& nums1, vector<int>& nums2) {\n        int mod=1e9+7;\n        long long int ans=0, sum1=0, sum2=0;\n        int i=0, j=0;\n        while(i<nums1.size() and j<nums2.size())\n        {\n            if(nums1[i] < nums2[j])\n                sum1 += nums1[i++]; \n            else if(nums1[i] > nums2[j])\n                sum2 += nums2[j++];\n            else\n            {\n                ans += nums1[i] + max(sum1, sum2);\n                i++;\n                j++;\n                sum1=0;\n                sum2=0;\n            }\n        }\n        while(i<nums1.size())\n            sum1 += nums1[i++];\n        while(j<nums2.size())\n            sum2 += nums2[j++];\n        ans += max(sum1, sum2);\n        ans = ans%mod;\n        return (int)ans;\n    }\n};\n```\n\nIf u find some mistake or have some doubts, feel free to ask.\nIf my post helps u, then please UPVOTE!\nHappy Coding!
['Two Pointers', 'Dynamic Programming', 'C++']