MyLeetcode/cpp_solutions/3984.cpp at main · Kaminyou/MyLeetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    vector<int> getPrimes() {
        vector<int> primes;
        vector<bool> visited(1001, false);
        for (int i = 2; i < 1001; ++i) {
            if (!visited[i]) primes.push_back(i);
            for (int j = 2; i * j < 1001; ++j) {
                visited[i * j] = false;
            }
        }
        return primes;
    }
    long long getAnswer(vector<int>& nums, int prime) {
        int n = nums.size();
        long long sum = 0;
        long long res = INT_MIN;
        for (int i = 0; i < n; ++i) {
            int val = nums[i];
            if (val % prime != 0) val = val * -1;
            sum += val;
            res = max(res, sum);
            if (sum < 0) sum = 0;
        }
        return res;
    }

    int divisibleGame(vector<int>& nums) {
        vector<int> primes = getPrimes();
        for (auto& num : nums) {
            if (num == 1) continue;
            bool isPrime = true;
            for (auto& prime : primes) {
                if (num % prime == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) primes.push_back(num);
        }
        long long maxPrime = -1;
        long long maxVal = LLONG_MIN;
        for (auto& prime : primes) {
            long long val = getAnswer(nums, prime);
            if (val > maxVal) {
                maxVal = val;
                maxPrime = prime;
            }
        }
        long long ans = maxVal * maxPrime;
        long long mod = 1e9 + 7;
        return (ans + mod) % mod;
    }
};