Algorithms
Medium
2786
2893
Visit Array Positions to Maximize Score
visit-array-positions-to-maximize-score
"""
You are given a 0-indexed integer array nums and a positive integer x.

You are initially at position 0 in the array and you can visit other positions according to the following rules:

 * If you are currently in position i, then you can move to any position j such that i < j.
 * For each position i that you visit, you get a score of nums[i].
 * If you move from a position i to a position j and the parities of nums[i] and nums[j] differ, then you lose a score of x.

Return the maximum total score you can get.

Note that initially you have nums[0] points.

Example 1:

Input: nums = [2,3,6,1,9,2], x = 5
Output: 13
Explanation: We can visit the following positions in the array: 0 -> 2 -> 3 -> 4.
The corresponding values are 2, 6, 1 and 9. Since the integers 6 and 1 have different parities, the move 2 -> 3 will make you lose a score of x = 5.
The total score will be: 2 + 6 + 1 + 9 - 5 = 13.

Example 2:

Input: nums = [2,4,6,8], x = 3
Output: 20
Explanation: All the integers in the array have the same parities, so we can visit all of them without losing any score.
The total score is: 2 + 4 + 6 + 8 = 20.


Constraints:

 * 2 <= nums.length <= 105
 * 1 <= nums[i], x <= 106
"""
class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        
You are given a 0-indexed integer array nums and a positive integer x.

You are initially at position 0 in the array and you can visit other positions according to the following rules:

 * If you are currently in position i, then you can move to any position j such that i < j.
 * For each position i that you visit, you get a score of nums[i].
 * If you move from a position i to a position j and the parities of nums[i] and nums[j] differ, then you lose a score of x.

Return the maximum total score you can get.

Note that initially you have nums[0] points.

Example 1:

Input: nums = [2,3,6,1,9,2], x = 5
Output: 13
Explanation: We can visit the following positions in the array: 0 -> 2 -> 3 -> 4.
The corresponding values are 2, 6, 1 and 9. Since the integers 6 and 1 have different parities, the move 2 -> 3 will make you lose a score of x = 5.
The total score will be: 2 + 6 + 1 + 9 - 5 = 13.

Example 2:

Input: nums = [2,4,6,8], x = 3
Output: 20
Explanation: All the integers in the array have the same parities, so we can visit all of them without losing any score.
The total score is: 2 + 4 + 6 + 8 = 20.


Constraints:

 * 2 <= nums.length <= 105
 * 1 <= nums[i], x <= 106


Please complete the code below to solve above prblem:
```python
class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        
```

my_solution = Solution()

test_input = { "nums": [2,3,6,1,9,2], "x": 5 }
assert my_solution.maxScore(**test_input) == 13

test_input = { "nums": [2,4,6,8], "x": 3 }
assert my_solution.maxScore(**test_input) == 20

test_input = { "nums": [38,92,23,30,25,96,6,71,78,77,33,23,71,48,87,77,53,28,6,20,90,83,42,21,64,95,84,29,22,21,33,36,53,51,85,25,80,56,71,69,5,21,4,84,28,16,65,7], "x": 52 }
assert my_solution.maxScore(**test_input) == 1545

test_input = { "nums": [18,13,60,61,57,21,10,98,51,3,13,36,72,70,68,62,52,83,63,63,53,42,59,98,95,48,22,64,94,80,14,14], "x": 2 }
assert my_solution.maxScore(**test_input) == 1633

test_input = { "nums": [90,87,79,59,91,19,96], "x": 51 }
assert my_solution.maxScore(**test_input) == 419

test_input = { "nums": [96,81,48,3,60,78,74,82,14,7,87,72,42,41,80,4,92,82,59,16,19,94,70,45,83,58,2,91,11,96,17,62,79,34,44,47,89,76,85,21,5,57,35,51], "x": 24 }
assert my_solution.maxScore(**test_input) == 1952

test_input = { "nums": [99,88,98,15,34,40,29,81,2,6,12,9,82,93,5,81,84,71,83,31,12,22,9,65,56,9,68,79,39,84,50,7,25,3,49], "x": 19 }
assert my_solution.maxScore(**test_input) == 1363

test_input = { "nums": [8,50,65,85,8,73,55,50,29,95,5,68,52,79], "x": 74 }
assert my_solution.maxScore(**test_input) == 470

test_input = { "nums": [45,9,20,89,18,94,12,51,38,77,100,95,46,1,76,41,8,90,82,33,92,32,76,43,6,61,85,40,63,10,74,18,44,43,17,100,17,33,100,77,97,8,99,85,88,9,63,31,32], "x": 68 }
assert my_solution.maxScore(**test_input) == 1694

test_input = { "nums": [87,23,53,57,21,60,68,84,66,49,48,61,32,95,71,11,15,61,10,86,50,53,38,20,63], "x": 92 }
assert my_solution.maxScore(**test_input) == 814

test_input = { "nums": [39,47,76,64,90,17,30,57,19,40,9,76,68,33,36,61,19,93,8,1,31,2,55,70,24,85,97,40,35,93,56,67,64,67,52,2,75,13,89,97], "x": 77 }
assert my_solution.maxScore(**test_input) == 1390

test_input = { "nums": [92,87,85,27,27,10,24,94,26,78,24,61,4,46,3,76,29,65,52,61,34,67,74,61,90,40,81,60,10,98,87,57,28,77,55,33,10,91,57,72,3,72,4,39,99], "x": 70 }
assert my_solution.maxScore(**test_input) == 1551

test_input = { "nums": [20,90,68], "x": 39 }
assert my_solution.maxScore(**test_input) == 178

test_input = { "nums": [43,100,72,33,45,9,51,10,22,42,7,74,41,68,100,24,20,20,79,30,99,82], "x": 1 }
assert my_solution.maxScore(**test_input) == 1060

test_input = { "nums": [100,87,29,94,56,41,53,98,34,17,52,3,54,51,22,39,37,9,76], "x": 40 }
assert my_solution.maxScore(**test_input) == 670

test_input = { "nums": [55,37,87,45,96,7,66,62,91,51,33,92,65,99], "x": 81 }
assert my_solution.maxScore(**test_input) == 625

test_input = { "nums": [2,75,65,43], "x": 39 }
assert my_solution.maxScore(**test_input) == 146

test_input = { "nums": [74,82,80,95,72,23,49,43,76,28,87,27,58,39,7,77,26,63,56,96,77,75,82,60,90,69,83,20,13,82,16,90,40,23,36,17,77,15,18,10], "x": 40 }
assert my_solution.maxScore(**test_input) == 1571

test_input = { "nums": [75,99,45,34,63,19,71,48,73,66,2,14,76,41,92,23,6,31,49,6,70,40,69,25,97,58,20,84,21,37,100,75,73,10,59,87,30], "x": 96 }
assert my_solution.maxScore(**test_input) == 1181

test_input = { "nums": [9,58,17,54,91,90,32,6,13,67,24,80,8,56,29,66,85,38,45,13,20,73,16,98,28,56,23,2,47,85,11,97,72,2,28,52,33], "x": 90 }
assert my_solution.maxScore(**test_input) == 886

test_input = { "nums": [96,89,30,38,58,26,47,52,27,77,87,92,6], "x": 83 }
assert my_solution.maxScore(**test_input) == 423

test_input = { "nums": [35,11,46,34,57,2,21,98,85,7,65,26,22,14,48,14,38,72,56,63,73,11,70,92,62,3,9,72,32,99,8,71,85,66,73,29,74,88,41,24,21,40,41,19,49,90], "x": 11 }
assert my_solution.maxScore(**test_input) == 1948

test_input = { "nums": [31,17,68,37,56,25,43,71,46,59,6,30,98,69,91], "x": 78 }
assert my_solution.maxScore(**test_input) == 443

test_input = { "nums": [53,49,57,84,69,39,97,78,19,42,10,16,16,62,79,74,49,59,21,29,76,6,14,64,76,29,8,27,26], "x": 80 }
assert my_solution.maxScore(**test_input) == 855

test_input = { "nums": [42,60,23,29,66,46,82,83,97,56,71,39,19,31,23,60,34,63,14,73,4,92,37,65,50,49,100,72,63], "x": 88 }
assert my_solution.maxScore(**test_input) == 943

test_input = { "nums": [79,60,100,62,25,2,86,9,66,67,20,14,92,27,93,52,12,67,9,8,69,21,31,77,71,52,60], "x": 84 }
assert my_solution.maxScore(**test_input) == 906

test_input = { "nums": [40,54,14,66,95,97,3,10,34,100,68,35,54,35,48,3,79,69,71,2,44,82,85,67,47,5,37,61,68,64,61,49,36,87,77,57,69,31,40,45,50,17,2,50,71], "x": 69 }
assert my_solution.maxScore(**test_input) == 1564

test_input = { "nums": [53,15,2,58,28,93,55,41,88,69,93,67,67,40,37,99,17,30,10,7,94,50,73,53,37,84,50,37,81,91,72,28,22,22,67], "x": 82 }
assert my_solution.maxScore(**test_input) == 1165

test_input = { "nums": [41,35,43,93,79,62,66,16,92,29,74,67,93,100,56,73], "x": 69 }
assert my_solution.maxScore(**test_input) == 714

test_input = { "nums": [67,9,2,39,28,92,99,62,37,75,3,53,26,32,76,14,88,16,68,56,60], "x": 91 }
assert my_solution.maxScore(**test_input) == 727

test_input = { "nums": [95,29,91,86,23,30,46,95,6,84,62,23,71,6,13,19,25,65,29,6,65,92], "x": 28 }
assert my_solution.maxScore(**test_input) == 886

test_input = { "nums": [74,47,86,24,44,91,88,64,37], "x": 24 }
assert my_solution.maxScore(**test_input) == 436

test_input = { "nums": [36,62,82,46,40], "x": 54 }
assert my_solution.maxScore(**test_input) == 266

test_input = { "nums": [66,28,100,33,15,47,80,43,61,16,10], "x": 3 }
assert my_solution.maxScore(**test_input) == 487

test_input = { "nums": [62,1,66,47,85,69,35,42,42,7,20,91], "x": 41 }
assert my_solution.maxScore(**test_input) == 436

test_input = { "nums": [8,23,19,37,12,78,25,62,99,88,86,27,1,78,40,57,5,62,12,93,10,42], "x": 60 }
assert my_solution.maxScore(**test_input) == 578

test_input = { "nums": [35,49,85,37,74,50,77,21,68,49,86,92,36,31,70,66,10,75,6,70,55,72,40,99,24,74,55,46,4,46,22,36,58,36,68,68,54,9,36,76,57,83,86,92,6,47,44,31], "x": 55 }
assert my_solution.maxScore(**test_input) == 1797

test_input = { "nums": [75,96,53,79,89,57,75,94,24,75,71,8,44,70,12,92,38,24,3,38,88,10], "x": 31 }
assert my_solution.maxScore(**test_input) == 1057

test_input = { "nums": [93,68,62,23,56,95,7,38,43,87,76,60,34,32,40,4,49,15,41,18,76,50], "x": 46 }
assert my_solution.maxScore(**test_input) == 776

test_input = { "nums": [53,78,79,81,75,36,35,37], "x": 61 }
assert my_solution.maxScore(**test_input) == 360

test_input = { "nums": [60,55,100,61,23,45,43,31], "x": 62 }
assert my_solution.maxScore(**test_input) == 301

test_input = { "nums": [98,48,29,44,96,57], "x": 40 }
assert my_solution.maxScore(**test_input) == 303

test_input = { "nums": [96,18,77,100,88,19,41,32,15,41,14], "x": 30 }
assert my_solution.maxScore(**test_input) == 405

test_input = { "nums": [46,69,20,84,52,23,13,52,68,49,99,23,14,60,56,71,68,43,44,66,96,58,94], "x": 6 }
assert my_solution.maxScore(**test_input) == 1208

test_input = { "nums": [85,12], "x": 79 }
assert my_solution.maxScore(**test_input) == 85

test_input = { "nums": [63,95,35,79,39,14,55,5,44,57,31,23,67,61,75,61,40,51,55,27,53,100,15,100,23,89,76,99,31,47,49,52,47], "x": 49 }
assert my_solution.maxScore(**test_input) == 1419

test_input = { "nums": [60,94,97,97,57,16,45,84,10,44,16], "x": 10 }
assert my_solution.maxScore(**test_input) == 584

test_input = { "nums": [24,28,63,5,13,83,2,15,81,34,9,10,54,88,12,36,81,87,81,42,56,82,85,85,31,47,29,59,21,55,73,31,80,75,61,70,82,90,23,44,71,94], "x": 57 }
assert my_solution.maxScore(**test_input) == 1665

test_input = { "nums": [92,7,95,1,79,49,58,77,54,12,38,18,9,23,75,98,76,86,40,33,22,14,62,67,60,36,67,51,85,100,75,30,55,63,28,100,94,4], "x": 89 }
assert my_solution.maxScore(**test_input) == 1282

test_input = { "nums": [76,24,85,30,37,86,3,50,94,19,48,95,31], "x": 93 }
assert my_solution.maxScore(**test_input) == 441

test_input = { "nums": [50,19,12,63,20,33,21,77,25,24,46,22,46,57,86,65,13,99,36,23,85,99,10], "x": 7 }
assert my_solution.maxScore(**test_input) == 949

test_input = { "nums": [68,26,50,20,54,30,12,66,30,75,31,89,78,30,17,38,97,15,43,39,82,25,3,78,66,6,68,86,29,20,99], "x": 97 }
assert my_solution.maxScore(**test_input) == 985

test_input = { "nums": [62,1,18,37,87,73,16], "x": 44 }
assert my_solution.maxScore(**test_input) == 233

test_input = { "nums": [35,60,95,31,19,87,19,37,78,82,81,96,23,58,93,96,92,41,48,67,90,70,6,97,6,2,77,47,34,17,51,15,13,93,12,46], "x": 1 }
assert my_solution.maxScore(**test_input) == 1895

test_input = { "nums": [21,29], "x": 68 }
assert my_solution.maxScore(**test_input) == 50

test_input = { "nums": [37,98,2,60,89,82,99,80,28,54,12,15,16,88,82,72,63,8,45,56,99,19,29,38,26,35], "x": 94 }
assert my_solution.maxScore(**test_input) == 813

test_input = { "nums": [84,8,44,48,85,77,18,34,17,46,53,84,52,77,12,94,18,67,46,45], "x": 44 }
assert my_solution.maxScore(**test_input) == 684

test_input = { "nums": [50,1,21,95,20,65,80,75,47,74,95,23,89,61,48,25,84,76,81,51,52,37,84,24,15,32,11,88], "x": 65 }
assert my_solution.maxScore(**test_input) == 982

test_input = { "nums": [54,2,22,17,41,23,51,16,5,42,12,77,9,71,92,87,78,50,14,74,72,42,90], "x": 52 }
assert my_solution.maxScore(**test_input) == 780

test_input = { "nums": [3,34,22,49,66,40,13,7,71,35,1,96,36,83,31,55,60,20,90,76,51,95,21,47,82,91,75,99,72,48,53,2,56,64], "x": 70 }
assert my_solution.maxScore(**test_input) == 1105

test_input = { "nums": [75,34,33,97,3,25,4,71,8,73], "x": 27 }
assert my_solution.maxScore(**test_input) == 377

test_input = { "nums": [27,91,78,7,48,79,23,34,17,42,94,85,48,36,26,57,53,10,38,32,45,89,74,5,35,39,9,59,71,39,1,60,39,50,47,47,48,74,71,91,85,86,22], "x": 74 }
assert my_solution.maxScore(**test_input) == 1292

test_input = { "nums": [26,97,16,94,49,98,78,84,76,21,75,88,22,49,34,98,7,94,100,98,72,70,47,6,56,8,50,9,37,37,34,36,48,95,8,63,35,81,26,57,91,4,83,38,64,45,98,51], "x": 86 }
assert my_solution.maxScore(**test_input) == 1919

test_input = { "nums": [14,64,4,14,94,58,67,15,79,26,66,34,47,42,20,67,5,21,63,73,44,96,29,72,26,20,84,84,62,39,93,53,13,35,32,82,22,58], "x": 87 }
assert my_solution.maxScore(**test_input) == 1252

test_input = { "nums": [42,98,75,46,10,21,10,35,4,59,100,78,62,51,84,99,92,2,4,12,59,8,42,85,86,81,20,1,43,41,56,2,30,25,21,56,43,82,38,45,89,54,15,63,69,20,64], "x": 45 }
assert my_solution.maxScore(**test_input) == 1442

test_input = { "nums": [99,80,22,56,93,18,65,63,8,16,80], "x": 39 }
assert my_solution.maxScore(**test_input) == 465

test_input = { "nums": [2,17,64,100,23,2,8,93,31,6,16,28,32,98,18,33,22,54,73,35,47,16,76,74,17,5,6,1,7,19,100,17,70,98,94,5,78,38,10,80], "x": 59 }
assert my_solution.maxScore(**test_input) == 1246

test_input = { "nums": [15,10,55,18,55,54,63,79,97,9,98,10,95,3,88,43,75,17,19,36,64,44,85,10,45,42,58,75,79,7,55,75,50,89,8,89,58,87,30,36,59,59,25], "x": 4 }
assert my_solution.maxScore(**test_input) == 2072

test_input = { "nums": [97,60,79,8,79,39,37,66,78,58,32,59,83,23,36,82,34,70,17,17,33,91,1,55,54,45,30,11,30,19,8,8,98,36,39,30,87,34,99,83,6,90], "x": 91 }
assert my_solution.maxScore(**test_input) == 1214

test_input = { "nums": [52,83,17,67,51,47,8,86,59,56,96,74,36,38,73,96,95,50,25,45,5,48,16,3,65,22,92,11,80,46,15], "x": 4 }
assert my_solution.maxScore(**test_input) == 1497

test_input = { "nums": [38,97,36,48,88,68,66,39,40,36,39,53,96,21,3,28,86,94,31,53,76,24,54,45,10,99,92,21,52,25,15,42,12,17,89,51], "x": 14 }
assert my_solution.maxScore(**test_input) == 1547

test_input = { "nums": [6,13,9], "x": 98 }
assert my_solution.maxScore(**test_input) == 6

test_input = { "nums": [52,66,40,14,6,26,37,93,23,2,40,10,42,1,85,22,45,46,16,14,70,76,48,100,68,85,72,31,15,56,65,61,83,90,31,31,2,27,55,91,50,32], "x": 18 }
assert my_solution.maxScore(**test_input) == 1679

test_input = { "nums": [8,60,58], "x": 18 }
assert my_solution.maxScore(**test_input) == 126

test_input = { "nums": [74,24,7,80,13,46,52,19,20,6,70,95,20,82,97,32,28,16,4,21,19,56,9,56,30,99,64,94,61,5,28,51,58,49,49,92,68,66,17,84,54], "x": 51 }
assert my_solution.maxScore(**test_input) == 1331

test_input = { "nums": [99,30,17,54,77,71,48,19,80,43,20,59,95,76,64,32,29,84,80,33,90,11,76,65,76,51,50,36,99], "x": 6 }
assert my_solution.maxScore(**test_input) == 1533

test_input = { "nums": [21,99,29,76,1,25,62,67,82,90,99,12,51,53,62,78,41,14,55,66,90,73,30,76,97], "x": 60 }
assert my_solution.maxScore(**test_input) == 935

test_input = { "nums": [59,78,89,17,43,89,21,43,73,76,68,94,69,76,26,3,86,65,45,29,68,53,41,87,79,37,11,55,82,97,9,48,64,13,56,56,60,22,22,50,23,51,14,36,2], "x": 81 }
assert my_solution.maxScore(**test_input) == 1655

test_input = { "nums": [5,2,24,57,9,5,71,90,20,80,9,99,45,27,60,7,65,23,55,46,49,57,7,22,28,35], "x": 77 }
assert my_solution.maxScore(**test_input) == 661

test_input = { "nums": [76,60,37,9,31,30,86,64,83,71,70,18,32,74,38,11,6,4,9,62,52,14,20,41,60,54,40,15,90,52,27,46,47,1,7,79,22,49,99,82], "x": 100 }
assert my_solution.maxScore(**test_input) == 1230

test_input = { "nums": [20,89,67,20,1,84,36,92,41,79,35,85,58,76,42,12,96,38,44,93,54,80,44,49,55,6,34,84,3,74,13], "x": 23 }
assert my_solution.maxScore(**test_input) == 1403

test_input = { "nums": [69,86,56,72,35,8,57,10,42,90,92,46,7,22,69,16,62,9,57,74,52,49,14,23,13,43,73,63,88,18,31,89,94,3,23,14,39,82,70,78], "x": 95 }
assert my_solution.maxScore(**test_input) == 1234

test_input = { "nums": [28,66,78,21,47,6,18,60,8,82,34,19,62,26,34,56,59,56,7,75,35,42,19,23,92,88,83,65,74,24,69,83,12,63,4,71,78,40,64,98,15,17,81,19], "x": 84 }
assert my_solution.maxScore(**test_input) == 1430

test_input = { "nums": [77,48,31,26], "x": 53 }
assert my_solution.maxScore(**test_input) == 108

test_input = { "nums": [33,69,10,90,86,82,66,19,28,33,9,98,87,7,7,17,69,79,85,65,31,38,75], "x": 21 }
assert my_solution.maxScore(**test_input) == 1042

test_input = { "nums": [16,99,70,71,62,42], "x": 83 }
assert my_solution.maxScore(**test_input) == 190

test_input = { "nums": [55,64,59,68,50,32,56,75,84,53,97,7,40,62,56,80,36,52,43,77,82,47,7,96,94,43,77,71,36,92], "x": 48 }
assert my_solution.maxScore(**test_input) == 1267

test_input = { "nums": [61,12,92,54,88,10,49,19,83,24,82,29,64,96,67,12,27,97,15,96,35,43,92,96,28,84,49,72,16,92,29,41], "x": 73 }
assert my_solution.maxScore(**test_input) == 1151

test_input = { "nums": [90,84,13,56,24,54,29,20], "x": 31 }
assert my_solution.maxScore(**test_input) == 328

test_input = { "nums": [94,12,26,83,92,8,64,21,80,32,47,71,30], "x": 66 }
assert my_solution.maxScore(**test_input) == 460

test_input = { "nums": [42,11,1], "x": 16 }
assert my_solution.maxScore(**test_input) == 42

test_input = { "nums": [22,56,65,84,34,80,56,63,22,52,94,29,99,45,20,66,50,62,44,10,3,70,13,23,99,99,71,61,11,28,48,66,41,4,5,18,22,44,36,92,10,90,20], "x": 36 }
assert my_solution.maxScore(**test_input) == 1706

test_input = { "nums": [6,45,84,69,49,47,49,13,6,25,82,38,1,4,99,68,89,78,53,29,73,96,71,58,88,18,97,61,37,80,20,93,77,38,84], "x": 40 }
assert my_solution.maxScore(**test_input) == 1336

test_input = { "nums": [85,71,5,91,31,75,36,4,42,81,92,42,40,14,57,72,33,66,4,1,26,81,45,56,64,76,43,39,53,9,37,38,53,26,2,55,6,70,9,45,35,60,73,38,62,58,3], "x": 86 }
assert my_solution.maxScore(**test_input) == 1343

test_input = { "nums": [32,53,27,49,7,40,22,85,53,46,28,95,59,85,78,16,15,63,24,64,90,9,84,9,66,41,75,8,22,53,72,29,15,32,49,29,37,66,82,63,59,58], "x": 70 }
assert my_solution.maxScore(**test_input) == 1221

test_input = { "nums": [76,100,47,98,31,46,73,18,40,46,4,70,33,43,58,21,72,24,97,17,18,61,86,9,8,96,54,55], "x": 43 }
assert my_solution.maxScore(**test_input) == 997

test_input = { "nums": [78,66,10,19,59,87,27,40,49,80,25,3,33,54,29,97,9,36,73,80,59,68], "x": 97 }
assert my_solution.maxScore(**test_input) == 626

test_input = { "nums": [13,26,3,19,21,43,33,62,32,61,40,22,56,69,15,21,10,87,84,66,26,35,54,64,7,53,32,14,7], "x": 76 }
assert my_solution.maxScore(**test_input) == 649

test_input = { "nums": [73,93,27,67,11,40,18,88,78,77,79,80,15,100,83,33,36,63,90,44,89,23,25,79,56,41,8,62,32,98,58], "x": 10 }
assert my_solution.maxScore(**test_input) == 1641

test_input = { "nums": [38,97,76,72,85,23,70,90,89,1,65,50,1,93,41,33,94,43,45,39,98,52,85,18,70,79,79,33,22,93,72,25,20,42,19,66,64,64,95,29,3,75,54,40,17,86,71,23,26,23], "x": 66 }
assert my_solution.maxScore(**test_input) == 1683