Dãy con đan dấu dài nhất - LCOJ: Luyện Code Online Judge

DANDAU - Dãy con đan dấu dài nhất

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

aprocoder

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Hãy lập trình tìm độ dài của dãy đan dấu lớn nhất trong mảng A có N phần tử!!!

Input

Dòng đầu tiên là số N(~ 1 \le N \le 10^5 ~)

N dòng tiếp theo là N phần tử ~ A_1 ~ , ~ A_2 ~ , ~ A_3 ~ , ... , ~ A_N ~ (~ - 10^5 \le A_i \le 10^5 ~)

Output

1 dòng là độ dài dãy con đan dấu dài nhất . Nếu không có dãy con đan dấu nào thì in ra -1

Sample

Input #1

Output #1

Hint

Ở test 1 , ta thấy dãy đan dấu dài nhất là 1 -2 3 có độ dài là 3 phần tử nên đáp án của test 1 là 3

Problem source: apok

Bình luận

Please read the guidelines before commenting.

CODE FULL AC CHO AE

#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <ios>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

#define pii pair&lt;int, int>
#define pll pair&lt;ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ull unsigned long long

#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

void fast_io() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
void solve() {}
int main() {
  fast_io();
  // freopen("books.inp", "r", stdin);
  // freopen("books.out", "w", stdout);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &i : a)
    cin >> i;
  int best = -1, cur_len = 1;
  for (int i = 1; i < n; i++) {
    if ((a[i - 1] < 0 && a[i] > 0) || (a[i - 1] > 0 && a[i] < 0)) {
      cur_len++;
    } else {
      best = max(cur_len, best);
      cur_len = 1;
    }
  }
  best = max(best, cur_len);
  if (best == 1){
    cout << -1;
    return 0;
  }
  cout << best;
  return 0;
}

0

0988440189 đã bình luận lúc 1, Tháng 7, 2025, 4:04

Ở bài này ta không xét số 0 đâu vì nó không phải số dương và số âm , nếu dùng 2 vòng for chắc chắn bị TLE test 2 , ta hãy nghĩ đơn giản là nếu kiểm tra (a[i]>0 và a[i-1]<0) hoặc ngược lại thì tăng biến temp++ và cập nhật maxLength=max(maxLength,temp) còn nếu không rơi vào truongef hợp này thì temp đưa về 1 (xuất phát từ phần tử bị sai ) .

-3

nguyennhat_18 đã bình luận lúc 20, Tháng 10, 2024, 12:19

test case 2 la gi ma ao ma the =))

0

0988440189 đã bình luận lúc 1, Tháng 7, 2025, 4:04

Nếu dùng 2 for bị TLE đó bạn.