Skip to content

Commit 1bfd915

Browse files
committed
improve doc
1 parent 0b95814 commit 1bfd915

File tree

1 file changed

+4
-4
lines changed
  • May-LeetCoding-Challenge/15-Maximum-Sum-Circular-Subarray

1 file changed

+4
-4
lines changed

May-LeetCoding-Challenge/15-Maximum-Sum-Circular-Subarray/README.md

+4-4
Original file line numberDiff line numberDiff line change
@@ -18,9 +18,9 @@ Explanation: [4,-1,2,1] has the largest sum = 6.
1818

1919
### Dynamic Programming
2020

21-
Denote by dp[i], the maximum subarray ending at nums[i].
21+
Denote by `dp[i]`, value of the maximum subarray ending at `nums[i]`.
2222

23-
Question: Given values of `dp[0 .. i - 1]`, how to compute `dp[i]` ?
23+
Question: Given `dp[0], dp[1], dp[i - 1]`, how to compute `dp[i]` ?
2424

2525
Answer: There are two possibilities:
2626

@@ -29,9 +29,9 @@ Answer: There are two possibilities:
2929
2. The maximum subarray ending at `nums[i]` is of length >= 2. In this case, it is an extension of the maximum subarray ending at `nums[i-1]`. In other words, `dp[i] = dp[i-1] + nums[i]`.
3030

3131

32-
By definition of dp[i], we have `dp[i] = max(nums[i], dp[i-1] + nums[i]) = nums[i] + max(0, dp[i-1]).`
32+
By definition of `dp[i]`, we have `dp[i] = max(nums[i], dp[i-1] + nums[i]) = nums[i] + max(0, dp[i-1]).`
3333

34-
Hence, here is the dp equation: `dp[i] = max(0, dp[i-1]) + nums[i]`. Moreover, since i-th element of dp[] only depends on (i-1)-th, the space complexity can be reduced to O(1).
34+
Hence, here is the dp equation: `dp[i] = max(0, dp[i-1]) + nums[i]`. Moreover, since i-th element of `dp[]` only depends on (i-1)-th, the space complexity can be reduced to O(1).
3535

3636

3737
### Complexity:

0 commit comments

Comments
 (0)