Given an array A[] of size N. In one operation only one subarray can be selected and replaced with the sum of the subarray. The task is to find the maximum size of the array after making it non-decreasing.
Examples:
Input: N = 5, A[] = {5, 1, 6, 6, 6}
Output: 4
Explanation: maximum size non-decreasing array, in this case, is {6, 6, 6, 6} which is obtained by replacing subarray(0, 1) = A[0] + A[1] = 6Input: N = 9, A[] = {5, 1, 6, 7, 7, 1, 6, 4, 5 }
Output: 6
Explanation: maximum size non-decreasing array, in this case, is {5, 7, 7, 7, 7, 9} which is obtained by replacing subarray(1, 2) = A[1] + A[2] = 7. Subarray(5, 6) = A[5] + A[6] = 7. Subarray(7, 8) = A[7] + A[8] = 9 Â Â Â Â Â
Approach: This problem can be solved using greedy approach based on the below observation:
Iterate linearly and consider the first element to be made up of subarray from 0 to i. Now to find the remaining elements, find the minimum size subarray whose sum is at least same as the previous element.
Follow the below steps to implement the idea:
- Let the first element of the final non-decreasing subarray be start.
- Iterate from i = 0 to N-1,
- Calculate start as the sum of the prefix of the array till i.
- For each value of start, iterate from j = i+1, and initialize temp=1
- temp store the value of the size of optimal non-decreasing array size for the current value of start.
- Consider subarray starting from j until the sum of the subarray is greater than equal to start.
- If a subarray is found then, increase the temp by 1 and update the start to the new subarray sum.
- Continue this iteration till j becomes N.
- The maximum value of temp among all iterations is the answer.
Below is the Implementation of the above approach:
C++
// C++ code to implement the approachÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to find maximum size non-decreasing arrayint findmaxsize(int N, int A[]){Â Â Â Â int ans = 0, sum = 0;Â Â Â Â for (int i = 0; i < N; i++) {Â Â Â Â Â Â Â Â int temp = 1;Â Â Â Â Â Â Â Â sum += A[i];Â Â Â Â Â Â Â Â int j = i + 1;Â
        // start stores the current starting number        int start = sum;        while (j < N) {            int count = 0;            int k = j;            while (k < N && count < start) {                count += A[k];                k++;            }Â
            // If subarray with max size is found            // just stop and merge            if (count >= start) {                start = count;                temp++;            }            j = k;        }        ans = max(ans, temp);    }Â
    // Return the final ans    return ans;}Â
// Driver Codeint main(){Â Â Â Â int A[] = { 5, 1, 6, 6, 6 };Â Â Â Â int N = sizeof(A) / sizeof(A[0]);Â
    // Function call    cout << findmaxsize(N, A) << endl;Â
    return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;Â
class GFG {Â
  // Function to find maximum size non-decreasing array  static int findmaxsize(int N, int A[])  {    int ans = 0, sum = 0;    for (int i = 0; i < N; i++) {      int temp = 1;      sum += A[i];      int j = i + 1;Â
      // start stores the current starting number      int start = sum;      while (j < N) {        int count = 0;        int k = j;        while (k < N && count < start) {          count += A[k];          k++;        }Â
        // If subarray with max size is found        // just stop and merge        if (count >= start) {          start = count;          temp++;        }        j = k;      }      ans = Math.max(ans, temp);    }Â
    // Return the final ans    return ans;  }Â
  // Driver Code  public static void main(String[] args)  {    int A[] = { 5, 1, 6, 6, 6 };    int N = A.length;Â
    // Function call    System.out.println(findmaxsize(N, A));  }}// This code is contributed by karandeep1234 |
Python3
# Python code to implement the approachÂ
# Function to find maximum size non-decreasing arraydef findmaxsize(N, A):Â Â Â Â ans, Sum = 0, 0Â
    for i in range(N):        temp = 1        Sum += A[i]        j = i + 1Â
        # start stores the current starting number        start = Sum        while(j < N):            count = 0            k = j            while(k < N and count < start):                count += A[k]                k += 1Â
            # If subarray with max size is found            # just stop and merge            if(count >= start):                start = count                temp += 1Â
            j = k        ans = max(ans, temp)Â
    # return the final ans    return ansÂ
Â
A = [5, 1, 6, 6, 6]N = len(A)# Function callprint(findmaxsize(N, A))Â
# This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approachÂ
using System;Â
public class GFG {Â
  // Function to find maximum size non-decreasing array  static int findmaxsize(int N, int []A)  {    int ans = 0, sum = 0;    for (int i = 0; i < N; i++) {      int temp = 1;      sum += A[i];      int j = i + 1;Â
      // start stores the current starting number      int start = sum;      while (j < N) {        int count = 0;        int k = j;        while (k < N && count < start) {          count += A[k];          k++;        }Â
        // If subarray with max size is found        // just stop and merge        if (count >= start) {          start = count;          temp++;        }        j = k;      }      ans = Math.Max(ans, temp);    }Â
    // Return the final ans    return ans;  }Â
  // Driver Code  public static void Main(string[] args)  {    int []A = { 5, 1, 6, 6, 6 };    int N = A.Length;Â
    // Function call    Console.WriteLine(findmaxsize(N, A));  }}// This code is contributed by AnkThon |
Javascript
// Javascript code to implement the approachÂ
// Function to find maximum size non-decreasing arrayfunction findmaxsize(N, A){Â Â Â Â let ans = 0, sum = 0;Â Â Â Â for (let i = 0; i < N; i++) {Â Â Â Â Â Â Â Â let temp = 1;Â Â Â Â Â Â Â Â sum += A[i];Â Â Â Â Â Â Â Â let j = i + 1;Â
        // start stores the current starting number        let start = sum;        while (j < N) {            let count = 0;            let k = j;            while (k < N && count < start) {                count += A[k];                k++;            }Â
            // If subarray with max size is found            // just stop and merge            if (count >= start) {                start = count;                temp++;            }            j = k;        }        ans = Math.max(ans, temp);    }Â
    // Return the final ans    return ans;}Â
// Driver CodeÂ
    let A = [ 5, 1, 6, 6, 6 ];    let N = A.length;Â
    // Function call    console.log(findmaxsize(N, A));Â
// This code is contributed by Pushpesh raj. |
Output
4
Time Complexity: O(N * N)Â
Auxiliary space: O(1)
Related Articles:
- Introduction to Arrays – Data Structure and Algorithm Tutorials
- Introduction to Greedy Algorithm – Data Structures and Algorithm Tutorials
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More on that Topic: geeksforgeeks.org/maximize-non-decreasing-array-size-by-replacing-subarray-with-sum/ […]
… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/maximize-non-decreasing-array-size-by-replacing-subarray-with-sum/ […]
… [Trackback]
[…] Find More on on that Topic: geeksforgeeks.org/maximize-non-decreasing-array-size-by-replacing-subarray-with-sum/ […]