Maximum Target Hits in Sequence

Find the longest consecutive sequence of successful target hits given a series of shooting scores

Understand the Problem

Problem Statement

In a shooting competition, whenever the target is hit, the score is increased by 1. When the target is missed the score is decreased by 1. Given N, the number of aims at the target and the score obtained at each of these N shots, print the longest number of successful hits in sequence. The score never falls below 0.

Constraints

1 ≤ N ≤ 999999
Score values are non-negative integers
The score sequence represents cumulative scoring over time
Each successful hit increases score by exactly 1
Each miss decreases score by exactly 1 (but never below 0)

Examples

Example 1

Input

20
0 1 0 0 1 2 1 2 3 4 3 2 3 4 5 6 7 8 7 6

Output

Explanation

The longest sequence of consecutive hits occurs from positions 12 to 17 (0-indexed), where the scores go from 2 to 8: 2→3→4→5→6→7→8. This represents 6 consecutive successful hits.

Solution

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    
    int scores[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &scores[i]);
    }
    
    int current_sequence = 0;
    int max_sequence = 0;
    
    for (int i = 1; i < n; i++) {
        if (scores[i] == scores[i-1] + 1) {
            current_sequence++;
            if (current_sequence > max_sequence) {
                max_sequence = current_sequence;
            }
        } else {
            current_sequence = 0;
        }
    }
    
    printf("%d\n", max_sequence);
    return 0;
}

Time:O(n) - single linear pass through the array

Space:O(n) - for storing the scores array

Approach:

The C solution reads the input using scanf, stores scores in an array, then iterates through the array starting from the second element. For each position, it checks if the current score is exactly one more than the previous score (indicating a successful hit). If so, it increments the current sequence counter and updates the maximum if needed. If not, it resets the current sequence to 0. Finally, it prints the maximum sequence length found.

Visual Explanation

Loading diagram...

All Problems