Maximum Sum of Good Subarray

Problem Statement

Maximum Sum of Good Subarray Problem Description You are given an array A of length N consisting of non-zero integers. A subarray is considered good if the LCM of the subarray (which is the smallest positive integer that is a multiple of all its elements) is not equal to the LCM of the entire array. Find the maximum sum of a good subarray. Since the answer can be very large return it modulo 10^9+7. Notes: It is given that in this problem the LCM of empty arrays is equal to 0. Input Format The first line contains an integer, N, denoting the number of elements in A. Each line i of the N subsequent lines (where 0 ≤ i < N) contains an integer describing A[i]. Examples Example 1: Input: 4 2 3 -3 -2 Output: 3 Explanation: N=4, A=[2,-3,-3,-2]. Possible subarrays are: [2], [3], [-3], [-2]. Among all these ones, the maximum subarray sum is 3. Example 2: Input: 5 1 2 3 4 5 Output: 10 Explanation: N=5, A=[1,2,3,4,5]. The LCM of the entire array is 60. If we pick the first 4 ones, we get an