Introduction
In this problem, we are given an Array of size N and we are required to maximize the subarray sum in minimum number of operations, we are supposed to pick an element from the array and change it to zero
Approach
we are going to maintain two variables and initialize it with -1 namely start and end, start is going to store the index of the first positive element from the array and end is going to store the index of the last positive element from the array,
After that we are going to iterate the array between the start and the end index and look for the negative element,if we find a negative element we are going to increase the counter, because the negative numbers in the array are the limiting factor to maximum subarray sum in an array and finally once the iteration ends we are going to print the count
Also, before we start iterating between start and end we are going to check whether the start variable is -1,if it stays -1 then we know the array has no positive elements and the maximum subarray sum is 0 and in that case we are going to print 0
Time Complexity
O(n) because we are only iterating the array once
Space Complexity
O(1) as we are only making use of variables and not any extra spaces to store our answers
Code
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0) {
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i<n; i++) {
arr[i] = sc.nextInt();
}
int count = 0, start = -1, end = -1;
for (int i = 0; i<n; i++) {
if(arr[i] > 0) {
start = i;
break;
}
}
for (int i = 0; i<n; i++) {
if(arr[i] > 0) {
end = i;
}
}
if(start == -1)
{
System.out.println(0);
continue;
}
for (int i = start; i<=end; i++) {
if(arr[i] < 0) {
count++;
}
}
System.out.println(count);
}
}
}