---
# System prepended metadata

title: LeetCode 2529. Maximum Count of Positive Integer and Negative Integer
tags: [Leetcode]

---

# LeetCode 2529. Maximum Count of Positive Integer and Negative Integer
[2529. Maximum Count of Positive Integer and Negative Integer](https://leetcode.com/problems/maximum-count-of-positive-integer-and-negative-integer/description/) (<font color=#00AF9B>Easy</font> 71.2%) 

<!-- 
(<font color=#00AF9B>Easy</font> 53.8%) 
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
 -->
    
- 限制 :

    <ul>
    <li><code>1 <= nums.length <= 2000</code></li>
    <li><code>-2000 <= nums[i] <= 2000</code></li>
    <li><code>nums is sorted in a non-decreasing order.</code></li>
    </ul>

- Solution
    這題我的想法是拆成兩邊，用 0 當作邊界。但用只有用一個 binary search 去實作，其實不太對。正確的寫法應該是要有兩個 binary search ，分別去找正數與負數，這樣的方法更好，可以符合 lg(n) 的速度。
    - 時間複雜度: $O(n)$
    - 空間複雜度: $O(1)$

- 程式碼 (7ms)
    ```c++=
    class Solution {
    public:
        int maximumCount(vector<int>& nums) {
            int min_index = 0, max_index = nums.size()-1;
            int mid_index;
            while(min_index <= max_index)
            {
                mid_index = (max_index - min_index) / 2 + min_index;
                if(nums[mid_index] == 0) break;
                if(nums[mid_index] < 0) min_index = mid_index + 1;
                if(nums[mid_index] > 0) max_index = mid_index - 1;
            }
            int neg_index = mid_index, pos_index = mid_index;
            while(neg_index >= 0 && nums[neg_index] >= 0)
                neg_index--;

            while(pos_index < nums.size() && nums[pos_index] <= 0)
                pos_index++;

            int neg_num = neg_index + 1, pos_num = nums.size() - pos_index;
            return max(neg_num, pos_num);
        }
    };
    ```
</details>