Блог пользователя kotadiyameet173

Автор kotadiyameet173, история, 6 часов назад, По-английски

You are given two arrays of size n. You need to choose the sub-array from the first array and replace it with a corresponding sub-array from the second array. Now, find the maximum consecutive sub-array sum in the modified first array.

Sample Input 1-

2

4 -2

1 2

Sample Output 1-

6

Sample Input 2-

8

-2 2 -3 1 -1 -1 1 0

4 -3 3 3 2 -5 3 4

Sample Output 2-

12

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
6 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by kotadiyameet173 (previous revision, new revision, compare).

»
5 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

dp[ind][can][cant]

can is 1 if we are replacing subarray ending at ind-1 and hence we can continue replacing now

cant is 1 if we have already replaced the subarray at index j<ind-1 and hence we can't replace now

»
4 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Someone already posted this https://mirror.codeforces.com/blog/entry/138331, you can find the solution in the comments