What if the problem was instead determining if you could generate a valid array with nums[index] == target?

To generate the array, set nums[index] to target, nums[index-i] to target-i, and nums[index+i] to target-i. Then, this will give the minimum possible sum, so check if the sum is less than or equal to maxSum.

n is too large to actually generate the array, so you can use the formula 1 + 2 + ... + n = n * (n+1) / 2 to quickly find the sum of nums[0...index] and nums[index...n-1].

Binary search for the target. If it is possible, then move the lower bound up. Otherwise, move the upper bound down.