# Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

```
class Solution:
def maxSubArray(self, nums):
cur_max, max_till_now = 0, -inf
for c in nums:
cur_max = max(c, cur_max + c)
max_till_now = max(max_till_now, cur_max)
return max_till_now
```

## Related Problems

There is an integer array nums sorted in ascending order (with **distinct** values).

Prior to being passed to your function, nums is **possibly rotated** at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (**0-indexed**). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums **after** the possible rotation and an integer target, return *the index of *target* if it is in *nums*, or *-1* if it is not in *nums.

You must write an algorithm with O(log n) runtime complexity.

A **transformation sequence** from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter.

Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.

sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return *all the ***shortest transformation sequences*** from* beginWord *to* endWord*, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words *[beginWord, s1, s2, ..., sk].

Given an array of **distinct** integers candidates and a target integer target, return *a list of all ***unique combinations*** of *candidates* where the chosen numbers sum to *target*.* You may return the combinations in **any order**.

The **same** number may be chosen from candidates an **unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you **must** take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.