遇到一个贪心算法问题，求解答。
现在有两个数组 a和 b，长度分别为n和m。你可以对两者进行任意次数（包括零次）的下述操作： 任选一段连续的区间[l, r]，将其替换为这段区间的所有数字的和。比如,对于[1,3,4,5,11,9]，你可以选择区间 [3,5]，并将其替换为 4+5+11=20，操作后的数组为 [1,3,20,9]。你现在需要通过上述操作将两个数组变成相同的数组，相同的定义是：对于两个数组a，b必须长度相同，不妨设为l，并且对于1<=i<=l，必有 a[i]=b[i]。如果这两个数组可以变成相同的数组，那么我们称这两个数组是相似数组，否则不是相似数组。我们并不在意操作的次数，我们只在意在这两个数组经过操作之后变成相同数组的时候最长的长度是多少，如果它们本来不相似请输出 -1。输入内容为四个部分，先两个数字n、m（1 <=n,m<=100000），分别表示数组a和b的长度，再分别输入含有 n 个数字的数组 a 和含有 m个数字的数组b，其中1<=a[i],b[i]<=1000000000。输出一个数字，表示最长的长度。
写回答
-
如果两个指针都等于各自数组的长度(即i==n&&j==m)，则返回结果(return ans)；如果两个指针仅有一个等于数组的长度（即i=n ||j=m)，则返回-1（表示不是相似数组 )；如果以上两个条件都不满足 ( 即两个指针都小于数组长度 )，则当前区间和更新为此时指向的元素 ( 即sum_a=a[i], sum_b=b[j])。如果sum_a 则数组a的指针向前移动（即i++），判断 i 是否越界(即i==n为真表示越界)，如果越界，那么返回-1(表示不是相似数组)，如果没越界，给区别和加上当前元素 (即sum_a+a[i])如果sum_a>sum_b:则数组b的指针向前移动（即 j++），判断j是否越界(即j==m为真表示越界)，如果越界，那么返回-1( 表示不是相似数组)，如果没越界，给区别和加上当前元素 (即sum_b+a[b])重复以上过程，即可求解。 则：输入：5 4 [7,2,5,11,13] [9,16 ,6,7] 输出：3
2021-12-23 18:27:30赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
