# LeetCode Weekly Contest 136

https://leetcode.com/contest/weekly-contest-136

## Robot Bounded In Circle

On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:

• "G": go straight 1 unit;
• "L": turn 90 degrees to the left;
• "R": turn 90 degress to the right.
The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

Example 1:

Example 2:

Example 3:

Note:

1. 1 <= instructions.length <= 100
2. instructions[i] is in {'G', 'L', 'R'}

## Flower Planting With No Adjacent

You have N gardens, labelled 1 to N. In each garden, you want to plant one of 4 types of flowers.

paths[i] = [x, y] describes the existence of a bidirectional path from garden x to garden y.

Also, there is no garden that has more than 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)-th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.

Example 1:

Example 2:

Example 3:

Note:

1. 1 <= N <= 10000
2. 0 <= paths.size <= 20000
3. No garden has 4 or more paths coming into or leaving it.
4. It is guaranteed an answer exists.

## Partition Array for Maximum Sum

Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

Example 1:

Note:

1. 1 <= K <= A.length <= 500
2. 0 <= A[i] <= 10^6

dp[i]表示到A[i]为止最大替换的和。对于前K个数，找到最大值覆盖整个子数组即可。当i>=K时，最多能向前覆盖K个数，因此可以找满足i-K<=j<i的最大dp[j]+max(A[j+1:i])*(i-j)