-[188. Best Time to Buy and Sell Stock IV](en/1-1000/188-best-time-to-buy-and-sell-stock-iv.md) was solved in_Python, JavaScript, Go_.

-[309. Best Time to Buy and Sell Stock with Cooldown](en/1-1000/309-best-time-to-buy-and-sell-stock-with-cooldown.md) was solved in_Python, JavaScript, Go_.

to here now

-[674. Longest Continuous Increasing Subsequence](en/1-1000/674-longest-continuous-increasing-subsequence.md) was solved in_Python, Java, JavaScript, C#_.

-[300. Longest Increasing Subsequence](en/1-1000/300-longest-increasing-subsequence.md) was solved in_Python, Java, JavaScript, C#_.

1. Change one vertex from`0` to`1` to make the largest island means combining the adjacent islands of a`0` vertex.

1. We can mark an island's lands with one same id (`island_id`), and mark another island's lands with another`island_id`. To mark a land, just change its value to the`island_id`.

1. Use a`map` (or an`array`) to map each`island_id` to its area (`land_count`).

1. Use a`map` (or an`array`) to map each`island_id` to its`area`.

1. How to calculate the area of an island? Using`Depth-First Search` or`Breadth-First Search`. See[695. Max Area of Island](695-max-area-of-island.md).

1. Iterate through each`0` (water), then sum the areas (`land_count`) of neighboring islands.

1. Iterate through each`0` (water), then sum the`areas` of neighboring islands.

1. Record the max area and return it.

from collectionsimport defaultdict

classSolution:

def__init__(self):

self.result=0

self.grid=None

self.land_count=0

self.land_counts= [0,0]# Since `island_id` starts from 2, the first two records will not be used

self.island_id=2

self.island_id_to_area= defaultdict(int)

deflargestIsland(self,grid: List[List[int]]) ->int:

self.grid= grid

max_area=0

for i, rowinenumerate(self.grid):

for j, valueinenumerate(row):

if value==1:

self.land_count=0

for iinrange(len(grid)):

for jinrange(len(grid[0])):

ifself.grid[i][j]==1:

self.depth_first_search(i, j)

self.island_id+=1

self.land_counts.append(self.land_count)

self.result=max(self.land_count,self.result)

has_water=False

self.island_id+=1

for i, rowinenumerate(grid):

for j, valueinenumerate(row):

if value==0:

self.result=max(

self.combined_islands_land_count(i, j),

self.result

)

returnself.result

for iinrange(len(grid)):

for jinrange(len(grid[0])):

ifself.grid[i][j]==0:

has_water=True

max_area=max(max_area,self.combined_islands_area(i, j))

ifnot has_water:

returnlen(grid)*len(grid[0])

return max_area

defdepth_first_search(self,i,j):

if i<0or i>=len(self.grid):

if j<0or j>=len(self.grid[0]):

if i<0or j<0or i>=len(self.grid)or j>=len(self.grid[0]):

ifself.grid[i][j]!=1:

self.grid[i][j]=self.island_id

self.land_count+=1

self.depth_first_search(i-1, j)

self.depth_first_search(i, j+1)

self.depth_first_search(i+1, j)

self.depth_first_search(i, j-1)

defcombined_islands_land_count(self,i,j):

used_island_ids=set()

count=1

count+=self.island_land_count(i-1, j, used_island_ids)

count+=self.island_land_count(i, j+1, used_island_ids)

count+=self.island_land_count(i+1, j, used_island_ids)

count+=self.island_land_count(i, j-1, used_island_ids)

return count

self.grid[i][j]=self.island_id

self.island_id_to_area[self.island_id]+=1

for a, bin [

(-1,0),

(0,-1), (0,1),

(1,0)

]:

m= i+ a

n= j+ b

self.depth_first_search(m, n)

defisland_land_count(self,i,j,used_island_ids):

if i<0or i>=len(self.grid):

if j<0or j>=len(self.grid[0]):

defcombined_islands_area(self,i,j):

island_ids=set()

for a, bin [

(-1,0),

(0,-1), (0,1),

(1,0)

]:

m= i+ a

n= j+ b

if m<0or n<0or m>=len(self.grid)or n>=len(self.grid[0]):

ifself.grid[m][n]!=0:

island_ids.add(self.grid[m][n])

ifself.grid[i][j]==0:

area=1

island_id=self.grid[i][j]

for island_idin island_ids:

area+=self.island_id_to_area[island_id]

if island_idin used_island_ids:

used_island_ids.add(island_id)

returnself.land_counts[island_id]

return area

- 647https://leetcode.cn/problems/palindromic-substrings/ very hard

- 516https://leetcode.cn/problems/longest-palindromic-subsequence/

- 417https://leetcode.com/problems/pacific-atlantic-water-flow/

- 222https://leetcode.cn/problems/count-complete-tree-nodes/

- 236https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

- 115https://leetcode.cn/problems/distinct-subsequences/

- 647https://leetcode.cn/problems/palindromic-substrings/https://leetcode.cn/problems/palindromic-substrings/submissions/597748845/

- 516https://leetcode.cn/problems/longest-palindromic-subsequence/

- 417https://leetcode.com/problems/pacific-atlantic-water-flow/

2005-02-09 day 2

1. Change one vertex from`0` to`1` to make the largest island means combining the adjacent islands of a`0` vertex.

1. We can mark an island's lands with one same id (`island_id`), and mark another island's lands with another`island_id`. To mark a land, just change its value to the`island_id`.

1. Use a`map` (or an`array`) to map each`island_id` to its area (`land_count`).

1. Use a`map` (or an`array`) to map each`island_id` to its`area`.

1. How to calculate the area of an island? Using`Depth-First Search` or`Breadth-First Search`. See[695. Max Area of Island](695-max-area-of-island.md).

1. Iterate through each`0` (water), then sum the areas (`land_count`) of neighboring islands.

1. Iterate through each`0` (water), then sum the`areas` of neighboring islands.

1. Record the max area and return it.

from collectionsimport defaultdict

classSolution:

def__init__(self):

self.result=0

self.grid=None

self.land_count=0

self.land_counts= [0,0]# Since `island_id` starts from 2, the first two records will not be used

self.island_id=2

self.island_id_to_area= defaultdict(int)

deflargestIsland(self,grid: List[List[int]]) ->int:

self.grid= grid

max_area=0

for i, rowinenumerate(self.grid):

for j, valueinenumerate(row):

if value==1:

self.land_count=0

for iinrange(len(grid)):

for jinrange(len(grid[0])):

ifself.grid[i][j]==1:

self.depth_first_search(i, j)

self.island_id+=1

self.land_counts.append(self.land_count)

self.result=max(self.land_count,self.result)

has_water=False

self.island_id+=1

for i, rowinenumerate(grid):

for j, valueinenumerate(row):

if value==0:

self.result=max(

self.combined_islands_land_count(i, j),

self.result

)

returnself.result

for iinrange(len(grid)):

for jinrange(len(grid[0])):

ifself.grid[i][j]==0:

has_water=True

max_area=max(max_area,self.combined_islands_area(i, j))

ifnot has_water:

returnlen(grid)*len(grid[0])

return max_area

defdepth_first_search(self,i,j):

if i<0or i>=len(self.grid):

if j<0or j>=len(self.grid[0]):

if i<0or j<0or i>=len(self.grid)or j>=len(self.grid[0]):

ifself.grid[i][j]!=1:

self.grid[i][j]=self.island_id

self.land_count+=1

self.depth_first_search(i-1, j)

self.depth_first_search(i, j+1)

self.depth_first_search(i+1, j)

self.depth_first_search(i, j-1)

defcombined_islands_land_count(self,i,j):

used_island_ids=set()

count=1

count+=self.island_land_count(i-1, j, used_island_ids)

count+=self.island_land_count(i, j+1, used_island_ids)

count+=self.island_land_count(i+1, j, used_island_ids)

count+=self.island_land_count(i, j-1, used_island_ids)

return count

self.grid[i][j]=self.island_id

self.island_id_to_area[self.island_id]+=1

for a, bin [

(-1,0),

(0,-1), (0,1),

(1,0)

]:

m= i+ a

n= j+ b

self.depth_first_search(m, n)

defisland_land_count(self,i,j,used_island_ids):

if i<0or i>=len(self.grid):

if j<0or j>=len(self.grid[0]):

defcombined_islands_area(self,i,j):

island_ids=set()

for a, bin [

(-1,0),

(0,-1), (0,1),

(1,0)

]:

m= i+ a

n= j+ b

if m<0or n<0or m>=len(self.grid)or n>=len(self.grid[0]):

ifself.grid[m][n]!=0:

island_ids.add(self.grid[m][n])

ifself.grid[i][j]==0:

area=1

island_id=self.grid[i][j]

for island_idin island_ids:

area+=self.island_id_to_area[island_id]

if island_idin used_island_ids:

used_island_ids.add(island_id)

returnself.land_counts[island_id]

return area