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 ansA = [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 approachusing 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!
