Maximize non reducing Array dimension by changing Subarray with sum

Given an array A[] of dimension N. In a single operation just one subarray will be chosen and changed with the sum of the subarray. The duty is to seek out the utmost dimension of the array after making it non-decreasing.

Examples:

Enter: N = 5, A[] = {5, 1, 6, 6, 6}
Output: 4
Rationalization: most dimension non-decreasing array, on this case, is {6, 6, 6, 6} which is obtained by changing subarray(0, 1) = A[0] + A[1] = 6

Enter: N = 9, A[] = {5, 1, 6, 7, 7, 1, 6, 4, 5 }
Output: 6
Rationalization: most dimension non-decreasing array, on this case, is {5, 7, 7, 7, 7, 9} which is obtained by changing subarray(1, 2) = A[1] + A[2] = 7. Subarray(5, 6) = A[5] + A[6] = 7. Subarray(7, 8) = A[7] + A[8] = 9          

Method: This drawback will be solved utilizing grasping strategy primarily based on the under statement:

Iterate linearly and take into account the primary ingredient to be made up of subarray from 0 to i. Now to seek out the remaining parts, discover the minimal dimension subarray whose sum is at the very least similar because the earlier ingredient.

Observe the under steps to implement the concept:

• Let the primary ingredient of the ultimate non-decreasing subarray be begin.
• Iterate from i = 0 to N-1,
  • Calculate begin because the sum of the prefix of the array until i.
  • For every worth of begin, iterate from j = i+1, and initialize temp=1
    • temp retailer the worth of the scale of optimum non-decreasing array dimension for the present worth of begin.
    • Think about subarray ranging from j till the sum of the subarray is larger than equal to begin.
    • If a subarray is discovered then, improve the temp by 1 and replace the begin to the brand new subarray sum.
  • Proceed this iteration until j turns into N.
• The utmost worth of temp amongst all iterations is the reply.

Beneath is the Implementation of the above strategy:

Time Complexity: O(N * N) 
Auxiliary area: O(1)

Associated Articles: