You are given 2 arrays. Choose a subarray from the first array (arr1) and replace it with the corresponding subarray from the second array (arr2). After replacing the subarray, calculate the maximum consecutive subarray sum of the modified first array. Find the maximum subarray sum you can get by doing this operation. You can do this operation only once.

N is 10^5 and ai [-1e9, 1e9]

Im not able to think of better than n^2. Pls help

Given an array nums containing N distinct integers and an integer K. You can perform any number of operations:

Select a sub-array of length K in nums and replace all the elements in the sub- array with the maximum number present in the current sub-array.

Find the minimum number of operations such that nums[1]=nums[n].

Input Format

The first line contains an integer N, where N denotes the number of elements in the array in the array. The second line contains N space- separated integers. The third line contains an integer, K.

Output Format

Print the minimum number of operations such that nums[1] nums[n].

Constraints:

•2sN,Ks10^5 • 1s am[i] $10^9

-I tried solving it but not able to find any optimal approach for the same.

Im recently struggling a lot with problems based on combinatorics. Can someone please share some good and useful resource for combinatorics? Will be really helpful.

Im finally able to break the newbie zone in last few of the rounds on CF..and I just want to share what really worked for me- and it is by giving virtual contests a lot. Yes giving virtual contests has increased my speed drastically during ongoing competitions and also solving just one question above your level is what I have done. So I really recommend people trying to break the newbie zone to try this it works..and I believe this method can even help to achieve much more higher ratings.