C - Variety Split Easy
Source: atcoder
Difficulty: 350

Problem Statement
This problem is a simplified version of Problem F.
You are given an integer sequence of length
N
:
A = (A_1, A_2, \ldots, A_N)
.
When splitting
A
at one position into two non-empty (contiguous) subarrays, find the maximum possible sum of the counts of distinct integers in those subarrays.
More formally, find the maximum sum of the following two values for an integer
i
such that
1 \leq i \leq N-1
: the count of distinct integers in
(A_1, A_2, \ldots, A_i)
, and the count of distinct integers in
(A_{i+1}, A_{i+2}, \ldots, A_N)
.
Constraints
2 \leq N \leq 3 \times 10^5
1 \leq A_i \leq N
(
1 \leq i \leq N
)
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1
A_2
\ldots
A_N
Output
Print the answer.
Sample Input 1
5
3 1 4 1 5
Sample Output 1
5
For
i=1
,
(3)
contains
1
distinct integer, and
(1,4,1,5)
contains
3
distinct integers, for a total of
4
.
For
i=2
,
(3,1)
contains
2
distinct integers, and
(4,1,5)
contains
3
distinct integers, for a total of
5
.
For
i=3
,
(3,1,4)
contains
3
distinct integers, and
(1,5)
contains
2
distinct integers, for a total of
5
.
For
i=4
,
(3,1,4,1)
contains
3
distinct integers, and
(5)
contains
1
distinct integer, for a total of
4
.
Therefore, the maximum sum is
5
for
i=2,3
.
Sample Input 2
10
2 5 6 5 2 1 7 9 7 2
Sample Output 2
8

C++ solution:
// abc397c_VarietySplitEasy.cc

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)

int main(){
  int n; cin >> n;
  vector<int> d(n),l(n),r(n);
  int cnt = 0,ans = 0;

  rep(i,n) cin >> d[i], d[i]--;
  rep(i,n){
    r[d[i]]++;
    if ( r[d[i]] == 1) cnt++;
  }

  rep(i,n){
    int t = d[i];
    if (l[t] ==0) cnt++;
    if (r[t] ==1) cnt--;
    l[t]++;r[t]--;
    ans = max(ans,cnt);
  }

  cout << ans << endl;
  return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    // 標準入力の準備
    reader := bufio.NewReader(os.Stdin)
    nStr, _ := reader.ReadString('\n')
    n, _ := strconv.Atoi(strings.TrimSpace(nStr))

    // 配列の入力
    a := make([]int, n)
    aStr, _ := reader.ReadString('\n')
    aSlice := strings.Fields(aStr)
    for i := 0; i < n; i++ {
        a[i], _ = strconv.Atoi(aSlice[i])
    }

    // 左側の種類数を計算
    suml := make([]int, n)
    vis := make([]bool, n+1)
    now := 0
    for i := 0; i < n; i++ {
        if !vis[a[i]] {
            now++
        }
        vis[a[i]] = true
        suml[i] = now
    }

    // 右側の種類数を計算
    sumr := make([]int, n)
    vis = make([]bool, n+1)
    now = 0
    for i := n - 1; i >= 0; i-- {
        if !vis[a[i]] {
            now++
        }
        vis[a[i]] = true
        sumr[i] = now
    }

    // 最大値を計算
    ans := 0
    for i := 0; i < n-1; i++ {
        if suml[i]+sumr[i+1] > ans {
            ans = suml[i] + sumr[i+1]
        }
    }

    fmt.Println(ans)
}

Java solution:
import java.io.*;
import java.util.*;
import java.util.function.*;

public class Main {
  private static int[] buildTable(int n, int[] as) {
    int[] counts = new int[n + 1];
    int[] output = new int[n  +1];
    output[0] = 0;
    for (int i = 0; i < n; i++) {
      int a = as[i];
      output[i + 1] = output[i] + (counts[a] == 0 ? 1 : 0);
      counts[a]++;
    }
    return output;
  }

  private static int[] reverse(int[] vs) {
    int n = vs.length;
    int[] output = new int[n];
    for (int i = 0; i < n; i++) {
      output[i] = vs[n - 1 - i];
    }
    return output;
  }

  private static int solve(int n, int[] as) {
    int[] table1 = buildTable(n, as);
    int[] table2 = reverse(buildTable(n, reverse(as)));
    int answer = 0;
    for (int i = 1; i < n; i++) {
      answer = Math.max(answer, table1[i] + table2[i]);
    }
    return answer;
  }

  private static void execute(ContestReader reader, ContestWriter out) {
    int n = reader.nextInt();
    int[] as = reader.nextInt(n);
    out.println(solve(n, as));
  }
  
  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    ContestWriter out = new ContestWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestWriter extends PrintWriter {
  ContestWriter(PrintStream printStream) {
    super(printStream);
  }

  public void printYN(boolean b) {
    println(b ? "Yes" : "No");
  }

  public void printYNList(List<Boolean> bList) {
    for (boolean b : bList) {
      printYN(b);
    }
  }

  public void printList(List<? extends Object> list) {
    for (Object object : list) {
      println(object);
    }
  }

  public void printListOneLine(List<? extends Object> list) {
    List<String> stringList = new ArrayList<>();
    for (Object object : list) {
      stringList.add(object.toString());
    }
    println(String.join(" ", stringList));
  }
}

class ContestReader {
  private static final int BUFFER_SIZE = 1024;
  
  private final InputStream stream;
  private final byte[] buffer;
  private int pointer;
  private int bufferLength;
  
  ContestReader(InputStream stream) {
    this.stream = stream;
    this.buffer = new byte[BUFFER_SIZE];
    this.pointer = 0;
    this.bufferLength = 0;
  }
  
  private boolean hasNextByte() {
    if (pointer < bufferLength) {
      return true;
    }
    
    pointer = 0;
    try {
      bufferLength = stream.read(buffer);
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
    return bufferLength > 0;
  }
  
  private int readByte() {
    if (hasNextByte()) {
      return buffer[pointer++];
    } else {
      return -1;
    }
  }
  
  private static boolean isPrintableChar(int c) {
    return 33 <= c && c <= 126;
  }
  
  public boolean hasNext() {
    while (hasNextByte() && !isPrintableChar(buffer[pointer])) {
      pointer++;
    }
    return hasNextByte();
  }
  
  public String next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    while(true) {
      int b = readByte();
      if (!isPrintableChar(b)) {
        break;
      }
      sb.appendCodePoint(b);
    }
    return sb.toString();
  }
  
  public String nextLine() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    while(true) {
      int b = readByte();
      if (!isPrintableChar(b) && b != 0x20) {
        break;
      }
      sb.appendCodePoint(b);
    }
    return sb.toString();
  }
  
  public char nextChar() {
    return next().charAt(0);
  }
  
  public int nextInt() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    
    int n = 0;
    boolean minus = false;
    
    {
      int b = readByte();
      if (b == '-') {
        minus = true;
      } else if ('0' <= b && b <= '9') {
        n = b - '0';
      } else {
        throw new NumberFormatException();
      }
    }
    
    while(true){
      int b = readByte();
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
    }
  }
  
  public long nextLong() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    
    long n = 0;
    boolean minus = false;
    
    {
      int b = readByte();
      if (b == '-') {
        minus = true;
      } else if ('0' <= b && b <= '9') {
        n = b - '0';
      } else {
        throw new NumberFormatException();
      }
    }
    
    while(true){
      int b = readByte();
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
    }
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public String[] next(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }
  
  public String[] nextLine(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLine();
    }
    return array;
  }
  
  public char[] nextChar(int n) {
    char[] array = new char[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextChar();
    }
    return array;
  }
  
  public int[] nextInt(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLong(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
  
  public double[] nextDouble(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }
  
  public char[] nextCharArray() {
    return next().toCharArray();
  }
  
  public String[][] next(int n, int m) {
    String[][] matrix = new String[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = next();
      }
    }
    return matrix;
  }
  
  public int[][] nextInt(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }
  
  public char[][] nextChar(int n, int m) {
    char[][] matrix = new char[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextChar();
      }
    }
    return matrix;
  }
  
  public long[][] nextLong(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }
  
  public double[][] nextDouble(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }
  
  public char[][] nextCharArray(int n) {
    char[][] matrix = new char[n][];
    for (int i = 0; i < n; i++) {
      matrix[i] = next().toCharArray();
    }
    return matrix;
  }
}

class Pair<T extends Comparable<T>, U extends Comparable<U>> implements Comparable<Pair<T, U>> {
  T first;
  U second;

  Pair(T first, U second) {
    this.first = first;
    this.second = second;
  }

  public int compareTo(Pair<T, U> p) {
    int tResult = first.compareTo(p.first);
    if (tResult != 0) {
      return tResult;
    }
    return second.compareTo(p.second);
  }
}

class MyAssert {
  public static void myAssert(boolean flag, String message) {
    if (!flag) {
      throw new RuntimeException(message);
    }
  }
 
  public static void myAssert(boolean flag) {
    myAssert(flag, "");
  }
}

JavaScript solution:
function Main(input) {
  const l = input.trim().split('\n');
  const n = parseInt(l[0]);
  const a = l[1].split(' ').map(v => parseInt(v));

  let s = Array(n - 1).fill(0);
  let c = Array(n).fill(0);
  let p = 0;
  for (let i = 0; i < n - 1; i ++) {
    if (c[a[i] - 1] === 0) {
      c[a[i] - 1] = 1;
      p ++;
    }
    s[i] = p;
  }  

  let t = Array(n - 1).fill(0);
  c = Array(n).fill(0);
  let q = 0;
  for (let i = 0; i < n - 1; i ++) {
    if (c[a[n - i - 1] - 1] === 0) {
      c[a[n - i - 1] - 1] = 1;
      q ++;
    }
    t[i] = q;
  }

  console.log(
    Math.max(...Array(n - 1).fill().map((_, i) => s[i] + t[n - i - 2]))
  );
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Python solution:
N = int(input())
A = list(map(int,input().split()))

left_set = set()
right_set = set()
maxp=0
count_left =[0]*N
count_right = [0]*N

for i in range(N):
    left_set.add(A[i])
    count_left[i]=len(left_set)

for i in range(N-1,-1,-1):
    right_set.add(A[i])
    count_right[i] = len(right_set)

for i in range(N-1):
    maxp = max(maxp,count_left[i]+count_right[i+1])
print(maxp)

Ruby solution:
input_n = gets.to_i
input_an = gets.split(" ").map(&:to_i)
v_arr = [0] * input_n
ln = [0]
s = 0
input_an.each do |an|
    if v_arr[an-1] == 0
        v_arr[an-1] = 1
        s += 1
    end
    ln.push s
end

s = 0
v_arr = [0] * input_n
rn = [0]
input_an.reverse.each do |an|
    if v_arr[an-1] == 0
        v_arr[an-1] = 1
        s += 1
    end
    rn.push s
end
rn = rn.reverse

sum = []
ln.each_with_index do |v, i|
    sum.push(v+rn[i])
end

puts sum.max