Skip to content

Instantly share code, notes, and snippets.

@jianminchen

jianminchen/max min - linear time algorithm - maximum number of chunks

Created January 31, 2018 06:44
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/7d1d3f8120b7d6ade4f60a4d2de4d6a8 to your computer and use it in GitHub Desktop.
Save jianminchen/7d1d3f8120b7d6ade4f60a4d2de4d6a8 to your computer and use it in GitHub Desktop.
Download ZIP
max min - linear time algorithm - maximum number of chunks
Raw
max min - linear time algorithm - maximum number of chunks
[2, 1, 3, 5, 4], size N, element of array is 1 to N, no duplicate
[2, 1], [3], [5, 4]
what is maximum number of chunk?
max[i] -> max to this point
min[i] -> min to this point from left
2,2,3,5,5
1,1,3,4,4
int chunks=0;
for(int i=0; i <nums.Length-1)
{
if(max[i] < min[i+1])
chunks++;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment