# Passes Problem

## 152 Maximum product subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest

* Need 2 variables to record positive and negative numbers
* Swap if num < -1
* Math.max & Math.min are used to handle corner case if num==0

```python
def maxProduct(self, nums: List[int]) -> int:
    ans = pProduct = nProduct = nums[0]
    
    for n in nums[1:]:
        if n < 0:
            pProduct, nProduct = nProduct, pProduct
        
        # nProduct is max either current num * previous product or number itself
        pProduct = max(n, pProduct*n)
        nProduct = min(n, nProduct*n)
        
        ans = max(ans, pProduct)       
    return ans
```

## 238. Product of Array Except Self

Given an array `nums` of *n* integers where *n* > 1,  return an array `output` such that `output[i]` is equal to the product of all the elements of `nums` except `nums[i]`.

```python
def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    ans = [1] * n
    
    p = nums[0]
    for i in range(1, n):
        ans[i] = p
        p *= nums[i]
        
    p = nums[n-1]
    for i in range(n-2, -1, -1):
        ans[i] *= p
        p *= nums[i]
        
    return ans
```

## 698. Partition to K Equal Sum Subset

Given an array of integers `nums` and a positive integer `k`, find whether it's possible to divide this array into `k` non-empty subsets whose sums are all equal.

[Explain](https://leetcode.com/problems/partition-to-k-equal-sum-subsets/discuss/108730/JavaC%2B%2BStraightforward-dfs-solution)

1. 可以處理負數
2. corner case: sum=0, 用 count > 0 紀錄加總個數

```python
"""
nums = {-1,1,0,0}, k = 4
nums = {-1,1}, k = 1
nums = {-1,1}, k = 2
nums = {-1,1,0}, k = 2
"""
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
    if sum(nums)%k != 0: return False
    s = sum(nums)/k
    
    # decrease 能較快收斂
    nums.sort(reverse=True)
    if nums[0] > s: return False
    
    while nums and nums[0] == s:
        nums.pop(0)
        k-=1
        
    visit = [0] * len(nums)
    return self.dfs(nums, 0, 0, 0, visit, k, s)


def dfs(self, nums, idx, cur_sum, count, visit, k, s):
    # 必定valid
    if k == 1: return True
    if cur_sum > s: return False
    if cur_sum == s and count >= 1:
        return self.dfs(nums, 0, 0, 0, visit, k-1, s)
    for i in range(idx, len(nums)):
        if visit[i]: continue
        visit[i] = 1      # 前面i皆visit過了
        if self.dfs(nums, i+1, cur_sum+nums[i], count+1, visit, k, s):
            return True
        visit[i] = 0
        
    return False
```

## 472. Concatenated Words

Given a list of words (**without duplicates**), please write a program that returns all concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

> ```
> Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
>
> Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
> ```

```python
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
    ans = []
    self.s = set(words)
    
    for w in words:
        self.s.remove(w)
        if self.isValid(w):
            ans.append(w)
        self.s.add(w)
    return ans


def isValid(self, word):
    if word in self.s: return True
    
    for i in range(1, len(word)):
        if word[:i] in self.s and self.isValid(word[i:]):
            return True
        
    return False
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/array/passes-problem.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.