Query to find length of the longest subarray consisting only of 1s

0 0 17 minutes read

Given a binary array arr[] of size N and a 2D array Q[][] containing K queries of the following two types:

1 : Print the length of the longest subarray consisting of 1s only.
2 X : Flip the element at the X^th index (1-based indexing) i.e change the element to ‘1’ if the current element is ‘0’ and vice versa.

Examples:

Input: N = 10, arr[] = {1, 1, 0, 1, 1, 1, 0, 0, 1, 1}, K=3, Q[][] = {{1}, {2, 3}, {1}}
Output: 3 6
Explanation:
Query 1: Length of the longest subarray of 1s only is 3.
Query 2: Flip the character ‘0’ at index 2 to ‘1’. Therefore, arr[] modifies to {1, 1, 1, 1, 1, 1, 0, 0, 1, 1}.
Query 3: Length of the longest subarray of 1s only is 6.

Input: N = 7, arr[] = {1, 1, 1, 1, 1, 1, 0}, K=3, Q[][]={{1}, {2, 7}, {1}}
Output: 6 7
Explanation:
Query 1: Length of the longest subarray of 1s only is 6.
Query 2: Flip the character ‘0’ at position 7. Therefore, the array arr[] modifies to {1, 1, 1, 1, 1, 1, 1}.
Query 3: Length of the longest subarray of 1s only is 7.

Naive Approach: The simplest approach to solve the problem is to traverse the array arr[] for each query and perform the given operations.

Below is the implementation of the above approach:

C++

// C++ Program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the longest subarray
// consisting of 1s only
int longestsubarray(int a[], int N)
{
    // Stores the maximum length of
    // subarray containing 1s only
    int maxlength = 0, sum = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // If current element is '1'
        if (a[i] == 1) {
 
            // Increment length
            sum++;
        }
 
        // Otherwise
        else {
 
            // Reset length
            sum = 0;
        }
 
        // Update maximum subarray length
        maxlength = max(maxlength, sum);
    }
    return maxlength;
}
 
// Function to perform given queries
void solveQueries(int arr[], int n,
                  vector<vector<int> > Q, int k)
{
 
    // Stores count of queries
    int cntQuery = Q.size();
 
    // Traverse each query
    for (int i = 0; i < cntQuery; i++) {
 
        if (Q[i][0] == 1) {
            cout << longestsubarray(arr, n) << " ";
        }
        else {
            // Flip the character
            arr[Q[i][1] - 1] ^= 1;
        }
    }
}
 
// Driver Code
int main()
{
    // Size of array
    int N = 10;
 
    // Given array
    int arr[] = { 1, 1, 0, 1, 1,
                  1, 0, 0, 1, 1 };
 
    // Given queries
    vector<vector<int> > Q = { { 1 }, { 2, 3 }, { 1 } };
 
    // Number of queries
    int K = 3;
 
    solveQueries(arr, N, Q, K);
}

Java

// Java Program for the above approach 
import java.util.*;
public class Main
{
  // Function to calculate the longest subarray 
  // consisting of 1s only 
  static int longestsubarray(int a[], int N) 
  { 
 
    // Stores the maximum length of 
    // subarray containing 1s only 
    int maxlength = 0, sum = 0; 
 
    // Traverse the array 
    for (int i = 0; i < N; i++) 
    { 
 
      // If current element is '1' 
      if (a[i] == 1) 
      { 
 
        // Increment length 
        sum++; 
      } 
 
      // Otherwise 
      else
      { 
 
        // Reset length 
        sum = 0; 
      } 
 
      // Update maximum subarray length 
      maxlength = Math.max(maxlength, sum); 
    } 
    return maxlength; 
  } 
 
  // Function to perform given queries 
  static void solveQueries(int arr[], int n, 
                           Vector<Vector<Integer>> Q, int k) 
  { 
 
    // Stores count of queries 
    int cntQuery = Q.size();
 
    // Traverse each query 
    for (int i = 0; i < cntQuery; i++)
    { 
 
      if (Q.get(i).get(0) == 1)
      { 
        System.out.print(longestsubarray(arr, n) + " "); 
      } 
      else
      { 
 
        // Flip the character 
        arr[Q.get(i).get(1) - 1] ^= 1; 
      } 
    } 
  }
 
  public static void main(String[] args) {
    // Size of array 
    int N = 10; 
 
    // Given array 
    int arr[] = { 1, 1, 0, 1, 1, 
                 1, 0, 0, 1, 1 }; 
 
    // Given queries 
    Vector<Vector<Integer>> Q = new Vector<Vector<Integer>>();
    Vector<Integer> v1 = new Vector<Integer>();
    Vector<Integer> v2 = new Vector<Integer>();
    Vector<Integer> v3 = new Vector<Integer>();
    v1.add(1);
    v2.add(2);
    v2.add(3);
    v3.add(1);
    Q.add(v1);
    Q.add(v2);
    Q.add(v3);
 
    // Number of queries 
    int K = 3; 
 
    solveQueries(arr, N, Q, K);
  }
}
 
// This code is contributed by divyesh072019

Python3

# Python Program for the above approach
 
# Function to calculate the longest subarray
# consisting of 1s only
def longestsubarray(a, N) :
     
    # Stores the maximum length of
    # subarray containing 1s only
    maxlength = 0
    sum = 0
 
    # Traverse the array
    for i in range(N):
 
        # If current element is '1'
        if (a[i] == 1) :
 
            # Increment length
            sum += 1
             
        # Otherwise
        else :
 
            # Reset length
            sum = 0
         
 
        # Update maximum subarray length
        maxlength = max(maxlength, sum)    
    return maxlength
 
# Function to perform given queries
def solveQueries(arr, n, Q, k) :
 
    # Stores count of queries
    cntQuery = len(Q)
 
    # Traverse each query
    for i in range(cntQuery):
 
        if (Q[i][0] == 1) :
            print(longestsubarray(arr, n), end = " ")
         
        else :
            # Flip the character
            arr[Q[i][1] - 1] ^= 1
         
# Driver Code
 
# Size of array
N = 10
 
# Given array
arr = [ 1, 1, 0, 1, 1,
        1, 0, 0, 1, 1] 
 
# Given queries
Q = [[1], [ 2, 3 ], [1]]  
 
# Number of queries
K = 3
solveQueries(arr, N, Q, K)
 
# This code is contributed by sanjoy_62

C#

// C# Program for the above approach 
using System;
using System.Collections.Generic;
class GFG 
{
     
    // Function to calculate the longest subarray 
    // consisting of 1s only 
    static int longestsubarray(int[] a, int N) 
    { 
       
        // Stores the maximum length of 
        // subarray containing 1s only 
        int maxlength = 0, sum = 0; 
       
        // Traverse the array 
        for (int i = 0; i < N; i++) 
        { 
       
            // If current element is '1' 
            if (a[i] == 1) 
            { 
       
                // Increment length 
                sum++; 
            } 
       
            // Otherwise 
            else
            { 
       
                // Reset length 
                sum = 0; 
            } 
       
            // Update maximum subarray length 
            maxlength = Math.Max(maxlength, sum); 
        } 
        return maxlength; 
    } 
       
    // Function to perform given queries 
    static void solveQueries(int[] arr, int n, 
                      List<List<int>> Q, int k) 
    { 
       
        // Stores count of queries 
        int cntQuery = Q.Count; 
       
        // Traverse each query 
        for (int i = 0; i < cntQuery; i++)
        { 
       
            if (Q[i][0] == 1)
            { 
                Console.Write(longestsubarray(arr, n) + " "); 
            } 
            else
            { 
               
                // Flip the character 
                arr[Q[i][1] - 1] ^= 1; 
            } 
        } 
    } 
 
  // Driver code
  static void Main() 
  {
       
    // Size of array 
    int N = 10; 
   
    // Given array 
    int[] arr = { 1, 1, 0, 1, 1, 
                  1, 0, 0, 1, 1 }; 
   
    // Given queries 
    List<List<int>> Q = new List<List<int>>();
    Q.Add(new List<int> { 1 });
    Q.Add(new List<int> { 2, 3 });
    Q.Add(new List<int> { 1 });
   
    // Number of queries 
    int K = 3; 
   
    solveQueries(arr, N, Q, K);
  }
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
 
// Javascript Program for the above approach
 
// Function to calculate the longest subarray
// consisting of 1s only
function longestsubarray(a, N)
{
    // Stores the maximum length of
    // subarray containing 1s only
    var maxlength = 0, sum = 0;
 
    // Traverse the array
    for (var i = 0; i < N; i++) {
 
        // If current element is '1'
        if (a[i] == 1) {
 
            // Increment length
            sum++;
        }
 
        // Otherwise
        else {
 
            // Reset length
            sum = 0;
        }
 
        // Update maximum subarray length
        maxlength = Math.max(maxlength, sum);
    }
    return maxlength;
}
 
// Function to perform given queries
function solveQueries(arr, n, Q, k)
{
 
    // Stores count of queries
    var cntQuery = Q.length;
 
    // Traverse each query
    for (var i = 0; i < cntQuery; i++) {
 
        if (Q[i][0] == 1) {
            document.write( longestsubarray(arr, n) + " ");
        }
        else {
            // Flip the character
            arr[Q[i][1] - 1] ^= 1;
        }
    }
}
 
// Driver Code
// Size of array
var N = 10;
// Given array
var arr = [1, 1, 0, 1, 1,
              1, 0, 0, 1, 1 ];
// Given queries
var Q = [ [ 1 ], [ 2, 3 ], [ 1 ] ];
// Number of queries
var K = 3;
solveQueries(arr, N, Q, K);
 
 
</script>

Output:

3 6

Time Complexity: (N * K)
Auxiliary Space: O(N)

Efficient Approach: The above approach can be optimized using Segment Tree data structure. The given problem can be solved based on the following observations:

It can be easily observed that one need at least three things for merging two nodes of a Segment Tree. Therefore, 3 segment trees are required, say MAX[], pref[], and suf[]. MAX[]: Stores the length of the longest subarray consisting only of 1s, pre[] and suf[] will store the longest length of prefix and suffix respectively.

Merging of two nodes can be done using the following:

MAX[i] = max(MAX[2*i], max(MAX[2*i + 1], suf[2*v + 1] + pref[2*i]))

pref[v] = max(pref[v * 2], pref[2 * v] + (pref[2 * v] == tm – tl + 1) * pref[v * 2 + 1])

suf[v] = max(suf[v * 2 + 1], suf[2 * v + 1] + suf[v * 2] * (suf[2 * v + 1] == tr – tm))

Here i, 2*i, 2*i + 1 are the current node, left child and right child respectively, and tl, tr is the current range

Follow the steps below to solve the problem:

For the query of type 1, print the root node, MAX[1] of the segment tree which contains the longest length of subarray consisting of only 1’s only in the range [1, N]
For the query of type 2, Flip the given position and update the segment tree.

Below is the implementation of the above approach:

C++

// C++ Program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
#define INF 1000000
 
// Arrays to store prefix sums, suffix
// and MAX's node respectively
int pref[500005];
int suf[500005];
int MAX[500005];
 
// Function to construct Segment Tree
void build(int a[], int tl, int tr, int v)
{
    if (tl == tr) {
 
        // MAX array for node MAX
        MAX[v] = a[tl];
 
        // Array for prefix sum node
        pref[v] = a[tl];
        // Array for suffix sum node
        suf[v] = a[tl];
    }
    else {
        int tm = (tl + tr) / 2;
        build(a, tl, tm, v * 2);
        build(a, tm + 1, tr, v * 2 + 1);
 
        // Calculate MAX node
        MAX[v] = max(MAX[v * 2],
                     max(MAX[v * 2 + 1],
                         suf[v * 2] + pref[v * 2 + 1]));
 
        pref[v] = max(pref[v * 2],
                      pref[2 * v]
                          + (pref[2 * v] == tm - tl + 1)
                                * pref[v * 2 + 1]);
 
        suf[v] = max(
            suf[v * 2 + 1],
            suf[2 * v + 1]
                + suf[v * 2] * (suf[2 * v + 1] == tr - tm));
    }
}
 
// Function to update Segment Tree
void update(int a[], int pos, int tl,
            int tr, int v)
{
    if (tl > pos || tr < pos) {
        return;
    }
 
    // Update at position
    if (tl == tr && tl == pos) {
 
        MAX[v] = a[pos];
        pref[v] = a[pos];
        suf[v] = a[pos];
    }
    else {
 
        // Update sums from bottom to the
        // top of Segment Tree
        int tm = (tl + tr) / 2;
        update(a, pos, tl, tm, v * 2);
        update(a, pos, tm + 1, tr, v * 2 + 1);
 
        // Update MAX tree
        MAX[v] = max(MAX[v * 2],
                     max(MAX[v * 2 + 1],
                         suf[v * 2] + pref[v * 2 + 1]));
        // Update pref tree
        pref[v] = max(pref[v * 2],
                      pref[2 * v]
                          + (pref[2 * v] == tm - tl + 1)
                                * pref[v * 2 + 1]);
        // Update suf tree
        suf[v] = max(suf[v * 2 + 1],
                     suf[2 * v + 1]
                         + (suf[2 * v + 1] == tr - tm)
                               * suf[v * 2]);
    }
}
 
// Function to perform given queries
void solveQueries(int arr[], int n,
                  vector<vector<int> > Q, int k)
{
    // Stores count of queries
    int cntQuery = Q.size();
 
    build(arr, 0, n - 1, 1);
 
    // Traverse each query
    for (int i = 0; i < cntQuery; i++) {
        if (Q[i][0] == 1) {
 
            // Print longest length of subarray in [1, N]
            cout << MAX[1] << " ";
        }
 
        else {
 
            // Flip the character
            arr[Q[i][1] - 1] ^= 1;
            update(arr, Q[i][1] - 1, 0, n - 1, 1);
        }
    }
}
 
// Driver Code
int main()
{
    // Size of array
    int N = 10;
 
    // Given array
    int arr[] = { 1, 1, 0, 1, 1,
                  1, 0, 0, 1, 1 };
 
    // Given queries
    vector<vector<int> > Q = { { 1 }, { 2, 3 }, { 1 } };
 
    // Number of queries
    int K = 3;
 
    solveQueries(arr, N, Q, K);
}

Java

// Java Program for the above approach
import java.util.*;
class GFG
{
static final int INF = 1000000;
 
// Arrays to store prefix sums, suffix
// and MAX's node respectively
static int []pref = new int[500005];
static int []suf = new int[500005];
static int []MAX = new int[500005];
 
// Function to construct Segment Tree
static void build(int a[], int tl, int tr, int v)
{
    if (tl == tr) {
 
        // MAX array for node MAX
        MAX[v] = a[tl];
 
        // Array for prefix sum node
        pref[v] = a[tl];
        // Array for suffix sum node
        suf[v] = a[tl];
    }
    else {
        int tm = (tl + tr) / 2;
        build(a, tl, tm, v * 2);
        build(a, tm + 1, tr, v * 2 + 1);
 
        // Calculate MAX node
        MAX[v] = Math.max(MAX[v * 2],
                     Math.max(MAX[v * 2 + 1],
                         suf[v * 2] + pref[v * 2 + 1]));
 
        pref[v] = Math.max(pref[v * 2],
                      pref[2 * v]
                          + (pref[2 * v] == (tm - tl + 1)?1:0)
                                * pref[v * 2 + 1]);
        suf[v] = Math.max(
            suf[v * 2 + 1],
            suf[2 * v + 1]
                + suf[v * 2] * (suf[2 * v + 1] == (tr - tm)?1:0));
    }
}
 
// Function to update Segment Tree
static void update(int a[], int pos, int tl,
            int tr, int v)
{
    if (tl > pos || tr < pos) {
        return;
    }
 
    // Update at position
    if (tl == tr && tl == pos) 
    {
        MAX[v] = a[pos];
        pref[v] = a[pos];
        suf[v] = a[pos];
    }
    else {
 
        // Update sums from bottom to the
        // top of Segment Tree
        int tm = (tl + tr) / 2;
        update(a, pos, tl, tm, v * 2);
        update(a, pos, tm + 1, tr, v * 2 + 1);
 
        // Update MAX tree
        MAX[v] = Math.max(MAX[v * 2],
                     Math.max(MAX[v * 2 + 1],
                         suf[v * 2] + pref[v * 2 + 1]));
        // Update pref tree
        pref[v] = Math.max(pref[v * 2],
                      pref[2 * v]
                          + (pref[2 * v] == (tm - tl + 1)?1:0)
                                * pref[v * 2 + 1]);
        // Update suf tree
        suf[v] = Math.max(suf[v * 2 + 1],
                     suf[2 * v + 1]
                         + (suf[2 * v + 1] == (tr - tm)?1:0)
                               * suf[v * 2]);
    }
}
 
// Function to perform given queries
static void solveQueries(int arr[], int n,
                  int[][] Q, int k)
{
    // Stores count of queries
    int cntQuery = Q.length;
    build(arr, 0, n - 1, 1);
 
    // Traverse each query
    for (int i = 0; i < cntQuery; i++)
    {
        if (Q[i][0] == 1)
        {
 
            // Print longest length of subarray in [1, N]
            System.out.print(MAX[1]+ " ");
        }
 
        else
        {
 
            // Flip the character
            arr[Q[i][1] - 1] ^= 1;
            update(arr, Q[i][1] - 1, 0, n - 1, 1);
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
    // Size of array
    int N = 10;
 
    // Given array
    int arr[] = { 1, 1, 0, 1, 1,
                  1, 0, 0, 1, 1 };
 
    // Given queries
    int [][]Q = { { 1 }, { 2, 3 }, { 1 } };
 
    // Number of queries
    int K = 3;
 
    solveQueries(arr, N, Q, K);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python 3 Program for the above approach
INF = 1000000
 
# Arrays to store prefix sums, suffix
# and MAX's node respectively
pref = [0 for i in range(500005)]
suf = [0 for i in range(500005)]
MAX = [0 for i in range(500005)]
 
# Function to construct Segment Tree
def build(a, tl,tr,v):
    global MAX
    global pref
    global suf
    if (tl == tr):
       
        # MAX array for node MAX
        MAX[v] = a[tl]
 
        # Array for prefix sum node
        pref[v] = a[tl]
         
        # Array for suffix sum node
        suf[v] = a[tl]
    else:
        tm = (tl + tr) // 2
        build(a, tl, tm, v * 2)
        build(a, tm + 1, tr, v * 2 + 1)
 
        # Calculate MAX node
        MAX[v] = max(MAX[v * 2], max(MAX[v * 2 + 1], suf[v * 2] + pref[v * 2 + 1]))
 
        pref[v] = max(pref[v * 2], pref[2 * v] + (pref[2 * v] == tm - tl + 1)* pref[v * 2 + 1])
 
        suf[v] = max(suf[v * 2 + 1],suf[2 * v + 1]+suf[v * 2] * (suf[2 * v + 1] == tr - tm))
 
# Function to update Segment Tree
def update(a,pos,tl,tr,v):
    global pref
    global suf
    global MAX
    if (tl > pos or tr < pos):
        return
 
    # Update at position
    if (tl == tr and tl == pos):
        MAX[v] = a[pos]
        pref[v] = a[pos]
        suf[v] = a[pos]
    else:
        # Update sums from bottom to the
        # top of Segment Tree
        tm = (tl + tr) // 2
        update(a, pos, tl, tm, v * 2)
        update(a, pos, tm + 1, tr, v * 2 + 1)
 
        # Update MAX tree
        MAX[v] = max(MAX[v * 2], max(MAX[v * 2 + 1], suf[v * 2] + pref[v * 2 + 1]))
         
        # Update pref tree
        pref[v] = max(pref[v * 2], pref[2 * v] + (pref[2 * v] == tm - tl + 1) * pref[v * 2 + 1])
         
        # Update suf tree
        suf[v] = max(suf[v * 2 + 1], suf[2 * v + 1] + (suf[2 * v + 1] == tr - tm) * suf[v * 2])
 
# Function to perform given queries
def solveQueries(arr, n, Q, k):
    global MAX
     
    # Stores count of queries
    cntQuery = len(Q)
    build(arr, 0, n - 1, 1)
 
    # Traverse each query
    for i in range(cntQuery):
        if (Q[i][0] == 1):
           
            # Print longest length of subarray in [1, N]
            print(MAX[1],end = " ")
 
        else:
            # Flip the character
            arr[Q[i][1] - 1] ^= 1
            update(arr, Q[i][1] - 1, 0, n - 1, 1)
 
# Driver Code
if __name__ == '__main__':
   
    # Size of array
    N = 10
     
    # Given array
    arr =  [1, 1, 0, 1, 1, 1, 0, 0, 1, 1]
     
    # Given queries
    Q =  [[1], [2, 3], [1]]
     
    # Number of queries
    K = 3
    solveQueries(arr, N, Q, K)
     
    # This code is contributed by SURENDRA_GANGWAR.

C#

// C# Program for the above approach
using System;
class GFG
{
   
static readonly int INF = 1000000;
 
// Arrays to store prefix sums, suffix
// and MAX's node respectively
static int []pref = new int[500005];
static int []suf = new int[500005];
static int []MAX = new int[500005];
 
// Function to construct Segment Tree
static void build(int []a, int tl, int tr, int v)
{
    if (tl == tr) 
    {
 
        // MAX array for node MAX
        MAX[v] = a[tl];
 
        // Array for prefix sum node
        pref[v] = a[tl];
       
        // Array for suffix sum node
        suf[v] = a[tl];
    }
    else
    {
        int tm = (tl + tr) / 2;
        build(a, tl, tm, v * 2);
        build(a, tm + 1, tr, v * 2 + 1);
 
        // Calculate MAX node
        MAX[v] = Math.Max(MAX[v * 2],
                     Math.Max(MAX[v * 2 + 1],
                         suf[v * 2] + pref[v * 2 + 1]));
        pref[v] = Math.Max(pref[v * 2],
                      pref[2 * v]
                          + (pref[2 * v] == (tm - tl + 1)?1:0)
                                * pref[v * 2 + 1]);
        suf[v] = Math.Max(
            suf[v * 2 + 1],
            suf[2 * v + 1]
                + suf[v * 2] * (suf[2 * v + 1] == (tr - tm)?1:0));
    }
}
 
// Function to update Segment Tree
static void update(int []a, int pos, int tl,
            int tr, int v)
{
    if (tl > pos || tr < pos) 
    {
        return;
    }
 
    // Update at position
    if (tl == tr && tl == pos) 
    {
        MAX[v] = a[pos];
        pref[v] = a[pos];
        suf[v] = a[pos];
    }
    else
    {
 
        // Update sums from bottom to the
        // top of Segment Tree
        int tm = (tl + tr) / 2;
        update(a, pos, tl, tm, v * 2);
        update(a, pos, tm + 1, tr, v * 2 + 1);
 
        // Update MAX tree
        MAX[v] = Math.Max(MAX[v * 2],
                     Math.Max(MAX[v * 2 + 1],
                         suf[v * 2] + pref[v * 2 + 1]));
         
      // Update pref tree
        pref[v] = Math.Max(pref[v * 2],
                      pref[2 * v]
                          + (pref[2 * v] == (tm - tl + 1)?1:0)
                                * pref[v * 2 + 1]);
         
      // Update suf tree
        suf[v] = Math.Max(suf[v * 2 + 1],
                     suf[2 * v + 1]
                         + (suf[2 * v + 1] == (tr - tm)?1:0)
                               * suf[v * 2]);
    }
}
 
// Function to perform given queries
static void solveQueries(int []arr, int n,
                  int[,] Q, int k)
{
   
    // Stores count of queries
    int cntQuery = Q.GetLength(0);
    build(arr, 0, n - 1, 1);
 
    // Traverse each query
    for (int i = 0; i < cntQuery; i++)
    {
        if (Q[i, 0] == 1)
        {
 
            // Print longest length of subarray in [1, N]
            Console.Write(MAX[1] + " ");
        }
 
        else
        {
 
            // Flip the character
            arr[Q[i, 1] - 1] ^= 1;
            update(arr, Q[i, 1] - 1, 0, n - 1, 1);
        }
    }
}
 
// Driver Code
public static void Main(String[] args)
{
   
    // Size of array
    int N = 10;
 
    // Given array
    int []arr = { 1, 1, 0, 1, 1,
                  1, 0, 0, 1, 1 };
 
    // Given queries
    int [,]Q = { { 1,0 }, { 2, 3 }, { 1,0 } };
 
    // Number of queries
    int K = 3;
    solveQueries(arr, N, Q, K);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript Program for the above approach
let INF = 1000000
 
// Arrays to store prefix sums, suffix
// and MAX's node respectively
let pref = new Array(500005);
let suf = new Array(500005);
let MAX = new Array(500005);
 
// Function to construct Segment Tree
function build(a, tl, tr, v)
{
    if (tl == tr) {
 
        // MAX array for node MAX
        MAX[v] = a[tl];
 
        // Array for prefix sum node
        pref[v] = a[tl];
        // Array for suffix sum node
        suf[v] = a[tl];
    }
    else {
        let tm = Math.floor((tl + tr) / 2);
        build(a, tl, tm, v * 2);
        build(a, tm + 1, tr, v * 2 + 1);
 
        // Calculate MAX node
        MAX[v] = Math.max(MAX[v * 2],
                    Math.max(MAX[v * 2 + 1],
                        suf[v * 2] + pref[v * 2 + 1]));
 
        pref[v] = Math.max(pref[v * 2],
                    pref[2 * v]
                        + (pref[2 * v] == tm - tl + 1)
                                * pref[v * 2 + 1]);
 
        suf[v] = Math.max(
            suf[v * 2 + 1],
            suf[2 * v + 1]
                + suf[v * 2] * (suf[2 * v + 1] == tr - tm));
    }
}
 
// Function to update Segment Tree
function update(a, pos, tl,tr, v)
{
    if (tl > pos || tr < pos) {
        return;
    }
 
    // Update at position
    if (tl == tr && tl == pos) {
 
        MAX[v] = a[pos];
        pref[v] = a[pos];
        suf[v] = a[pos];
    }
    else {
 
        // Update sums from bottom to the
        // top of Segment Tree
        let tm = Math.floor((tl + tr) / 2);
        update(a, pos, tl, tm, v * 2);
        update(a, pos, tm + 1, tr, v * 2 + 1);
 
        // Update MAX tree
        MAX[v] = Math.max(MAX[v * 2],
                    Math.max(MAX[v * 2 + 1],
                        suf[v * 2] + pref[v * 2 + 1]));
        // Update pref tree
        pref[v] = Math.max(pref[v * 2],
                    pref[2 * v]
                        + (pref[2 * v] == tm - tl + 1)
                                * pref[v * 2 + 1]);
        // Update suf tree
        suf[v] = Math.max(suf[v * 2 + 1],
                    suf[2 * v + 1]
                        + (suf[2 * v + 1] == tr - tm)
                            * suf[v * 2]);
    }
}
 
// Function to perform given queries
function solveQueries(arr, n, Q, k)
{
    // Stores count of queries
    let cntQuery = Q.length;
 
    build(arr, 0, n - 1, 1);
 
    // Traverse each query
    for (let i = 0; i < cntQuery; i++) {
        if (Q[i][0] == 1) {
 
            // Print longest length of subarray in [1, N]
            document.write(MAX[1] + " ");
        }
 
        else {
 
            // Flip the character
            arr[Q[i][1] - 1] ^= 1;
            update(arr, Q[i][1] - 1, 0, n - 1, 1);
        }
    }
}
 
// Driver Code
 
// Size of array
let N = 10;
 
// Given array
let arr = [ 1, 1, 0, 1, 1, 1, 0, 0, 1, 1 ];
 
// Given queries
let Q = [ [ 1 ], [ 2, 3 ], [ 1 ] ];
 
// Number of queries
let K = 3;
 
solveQueries(arr, N, Q, K);
 
// This code is contributed by shinjanpatra
</script>

Output:

3 6

Time Complexity: O(max(K*log(N), N*log(N)))
Auxiliary Space: O(4*N)

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 zambiatek!