How data structures kill complexity from O (n ^ 3) to O (n)

Many beginners are not very clear about how the data structure kills the complexity from O (n ^ 3) to O (n). In order to help you solve this problem, the following editor will explain it in detail. People with this need can come and learn. I hope you can gain something.

Recently, I just did this problem on LEETCODE (53.Maximum Subarray). It occurred to me that there are examples of this topic in the data structure, so I would like to make a summary.

Topic: give you an array so that you can find the sum of the largest subsequences.

For example, the sum of the largest subsequences is 6 (4) in the input [- 2, 1, 4, 4, 4, 1, 2, and 4].

PS: do you remember how the time complexity was calculated?

Based on the worst-case scenario, the order of magnitude is supreme. Nested multiplication, sibling addition.

Functions / definitions that may need to be explained:

Max (aforme b): returns the larger of the ameme b.

Vector&nums: pass in a vector library, and if you are new to it, you can temporarily think of it as an array (it is different from an array, of course).

All of the following code is only part of the function.

The complete code can be seen in: https://github.com/Ckend/GongZhongHao/tree/master/2.27.

O (n ^ 3)

First of all, the most direct way of thinking is to find the sum of each subsequence. The function of temp is: 1. Find the sum of each subsequence, 2. Each time the calculation is finished, it will be compared with result, and if it is larger than result, the value will be assigned to result. Every time these two operations finish, temp clears zero.

Int MaxSubSequenceSum (std::vector&nums) {

Int temp = 0, result = 0

For (int I = 0; I < nums.size (); + + I) {

For (int j = I; j < nums.size (); + + j) {

Temp = 0

For (int k = I; k