C++ Tìm số mảng con có tổng lẻ

Mảng con là phần liên tiếp của mảng. Tìm số mảng con có tổng lẻ. Ví dụ:

Input: {9,8,7,6,5} → Output: 9
Các mảng con tổng lẻ: {9}, {7}, {5}, {9,8}, {8,7}, {7,6}, {6,5}, {8,7,6}, {9,8,7,6,5}

Phương pháp vét cạn

Kiểm tra tổng mọi mảng con O(n²).

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n=5, a[]={9,8,7,6,5}, cnt=0;
    for (int i=0; i

Kết quả
Số mảng con tổng lẻ: 9

Phương pháp hiệu quả O(n)
Duyệt mảng, giữ count_even, count_odd = số mảng con kết thúc tại i có tổng chẵn/lẻ. Gặp số lẻ → swap(count_even, count_odd), count_odd++. Gặp số chẵn → count_even++. Cộng count_odd vào kết quả.

Ví dụ
#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[]={9,8,7,6,5}, n=5;
    int odd=0, even=0, result=0;
    for (int i=0; i

Kết quả
Số mảng con tổng lẻ: 9

Kết luận
Đã trình bày 2 cách: vét cạn O(n²) và tối ưu O(n) theo dõi parity mảng con kết thúc tại i. Hy vọng hữu ích.