TheRealSamuel/LeetCodeProblem

1 2class MySuite extends munit.FunSuite {3  4  test("test1") {5    assertEquals(Main.numberOfSubsequences(List(1,2,3,4,3,6,1)), 1)6  }7 8  test("test2") {9    assertEquals(Main.numberOfSubsequences(List(3,4,3,4,3,4,3,4)), 3)10  }11 12  test("test3") {13    assertEquals(Main.numberOfSubsequences(157,123,292,72,538,948,379,889,202,45,444,413,532,36,787,657,764,805,24,93,314,864,344,897,565,971,940,888,931,970,526,531,156,404,772,391,939,892,533,579,767,290,576,119,412,571,932,987,284,137,842,659,79,914,83,258,63,315,525,944,439,145,609,953,544,593,252,322,360,710,502,476,664,47,872,248,387,715,258,733,652,741,813,678,624,327,784,133,92,191,877,540,573,485,489,118,824,88,506,676,335,793,123,93,37,570,50,633,392,356,976,634,712,953,249,408,202,622,598,102,475,33,886,208,531,47,931,436,835,377,913,232,992,95,814,71,77,738,256,999,369,871,328,575,352,376,895,833,557,485,794,632,208,81,304,586,270,715,385,52,635,395,746,773,88,843,801,539,627,829,831,221,784,479,598,907,740,905,979,314,827,207,182,44,772,700,690,590,890,593,902,689,111,365,36,34,462,542,674,620,858,203,568,657,993,284,862,888,178,359,879,712,365,671,559,366,392,226,754,755,101,411,500,717,622,531,383,548,718,969,317,258,325,833,699,360,113,234,355,924,123,708,775,818,54,637,588,415,599,137,464,577,790,996,636,354,612,232,946,343,673,282,360,751,204,246,904,778,352,797,33,257,40,949,718,32,113,146,147,428,564,147,854,81,986,596,687,265,559,417,70,199,969,631,317,98,981,307,111,18,865,856,688,658,732,808,610,10,622,258,220,571,273,703,631,954,498,272,878,549,743,703,869,406,833,232,677,929,724,263,108,462,772,896,574,712,75,479,845,169,877,652,634,603,213,37,202,619,422,624,164,887,163,82,326,898,465,878,118,880,410,824,887,564,540,515,807,280,266,115,418,155,509,822,696,575,643,347,314,744,341,983,279,670,724,953,113,68,542,212,336,536,392,804,507,855,887,37,83,160,410,915,730,978,753,330,241,92,535,44,626,807,690,835,551,67,577,844,370,787,254,775,315,431,767,150,183,538,922,558,48,268,508,115,311,828,37,649,604,813,779,789,285,804,212,686,416,959,807,387,24,977,464,230,796,392,776,835,843,246,347,635,359,569,404,349,931,987,100,102,990,754,666,880,250,206,744,23,719,412,467,807,796,312,346,481,210,855,72,489,479,525,611,539,534,995,429,444,676,770,793,12,586,245,131,92,370,382,944,41,627,94,107,731,58,183,226,530,431,283,438,919,697,211,911,748,339,357,797,727,938,619,279,453,360,721,984,428,603,865,277,944,548,42,611,106,557,929,631,525,278,315,891,380,782,998,531,750,106,347,565,953,35,204,114,327,886,508,514,938,229,230,710,4,951,484,269,280,11,613,865,750,185,378,582,948,845,825,16,628,493,371,84,718,127,206,998,783,259,859,970,157,360,452,605,385,404,106,637,783,950,562,735,288,796,371,738,775,334,886,204,188,290,365,75,220,116,513,361,821,793,900,992,825,503,964,446,815,106,279,983,310,970,429,584,258,293,880,903,326,607,704,431,838,167,632,969,82,769,304,800,101,187,319,960,214,208,175,857,82,862,663,13,495,299,731,306,73,869,8,444,87,55,622,118,452,245,280,546,989,762,330,717,471,327,680,998,328,215,681,581,115,39,67,529,835,591,350,559,779,566,513,318,362,914,258,986,520,289,266,477,490,857,185,687,305,343,908,795,404,567,123,102,231,871,670,162,961,266,80,335,702,342,268,517,173,61,544,687,671,335,155,606,810,920,783,52,963,964,921,724,704,953,628,247,650,433,901,144,125,648,888,286,445,379,430,309,723,986,535,464,820,323,987,797,781,721,562,540,664,952,485,500,987,480,72,861,31,922,122,6,674,863,300,755,88,260,50,478,391,626,663,241,66,535,575,344,981,289,759,457,728,848,739,154,733,408,455,356,328,79,410,485,4,554,584,562,63,902,444,21,237,258,532,350,880,257,242,250,676,522,43,816,773,810,300,445,419,34,307,971,925,725,243,177,392,510,35,534,720,925,420,632,328,752,569,835,448,443,346,941,220,209,439,257,311,192,271,141,876,647,479,98,102,694,770,201,181,478,970,451,61,280,836,255,704,712,321,899,200,461,53,181,567,869,909,270,830,351,245,222,771,3,398,948,697,476,944,229,881,382,902,405,834,422,627,899,55,736,196,921,293,933,278,378,471,615,359,62,119,405,583,998,710,503,470,378,498,773,40,240,439,341,785,444,282,619,465,963,206,451,141,517,958,111,855,851,712,105,158,327,423,444,977,841,237,804,605,964,406,617), 304006)14  }15 16  test("test4") {17    assertEquals(Main.numberOfSubsequences(822,69,148,353,692,228,730,335,775,94,77,117,605,943,577,520,87,363,995,720,520,785,994,439,111,903,222,94,482,958,679,117,610,55,580,746,105,175,249,612,834,766,624,615,128,536,756,419,455,18,89,44,281,132,626,68,25,603,229,10,832,158,658,628,590,571,150,606,818,274,106,396,921,502,717,95,680,386,536,307,866,864,268,429,476,826,527,845,148,450,1,947,80,680,474,188,904,92,645,218,838,576,331,145,69,894,716,235,346,399,661,571,430,853,539,713,466,345,616,963,292,16,371,334,464,550,614,709,899,288,793,186,428,129,617,166,391,901,318,674,431,750,546,499,4,487,809,325,620,371,891,393,118,665,602,511,285,225,186,450,866,320,381,203,155,276,353,35,392,243,885,783,511,660,88,161,377,183,135,114,148,661,951,490,705,728,275,754,944,506,226,331,90,194,11,792,253,369,486,193,262,647,988,713,925,876,796,836,832,692,543,808,918,512,661,110,225,597,877,681,238,213,343,987,986,397,550,649,41,884,791,214,124,796,70,484,709,901,63,415,769,360,702,21,547,929,399,863,394,250,846,810,976,648,970,889,402,44,373,927,686,109,558,310,61,919,519,952,910,980,874,747,315,423,482,623,612,507,863,757,624,378,867,618,567,714,721,123,308,420,467,977,736,239,674,16,694,353,506,802,604,301,344,656,525,149,175,748,280,46,841,438,723,67,680,790,969,455,133,745,882,29,578,480,51,841,527,345,261,597,469,447,586,874,211,827,65,772,258,37,612,441,691,726,337,137,414,147,427,398,219,28,46,508,642,144,139,813,411,88,302,970,960,51,337,795,203,665,298,387,218,490,984,532,57,800,664,703,654,689,697,150,988,188,302,20,40,395,553,343,381,225,550,359,619,283,921,92,766,765,687,28,862,750,516,963,569,962,259,934,655,751,443,983,154,758,28,339,502,104,471,829,694,339,396,159,830,470,196,530,673,246,9,496,338,565,427,111,406,878,985,616,392,522,851,721,119,287,324,807,178,262,187,437,464,697,658,785,953,297,239,136,873,324,146,527,85,451,722,985,121,479,292,570,134,23,606,838,160,72,683,133,69,793,364,430,442,355,663,92,851,168,967,909,311,687,37,29,780,48,530,765,580,828,93,5,48,758,819,884,221,309,446,868,984,701,945,119,747,200,84,544,326,376,521,883,681,923,615,394,916,68,568,999,40,839,84,422,617,5,686,444,740,181,542,744,270,437,134,769,781,312,928,889,115,119,446,533,677,968,404,539,598,802,140,761,592,114,604,719,585,21,973,679,572,9,857,168,779,298,363,770,346,887,852,909,799,549,566,985,300,681,873,815,290,801,837,167,95,552,126,561,688,828,324,444,400,100,741,61,465,187,244,750,75,157,868,405,379,846,552,921,671,685,731,272,542,692,971,835,130,284,670,272,30,371,533,119,480,910,986,365,501,393,692,764,913,768,562,105,154,94,169,241,732,964,928,949,639,653,116,575,866,81,393,347,319,467,936,178,901,968,674,594,10,453,766,965,975,825,781,809,253,535,334,624,480,537,479,303,507,116,263,614,536,800,95,875,739,142,459,219,525,184,256,367,614,476,890,389,662,169,207,898,4,540,710,303,720,235,172,123,264,672,437,547,55,178,859,160,633,756,245,808,281,592,763,115,35,977,437,105,21,764,500,819,634,717,822,427,362,452,944,601,578,971,141,598,85,474,797,416,506,742,945,449,398,506,495,130,583,693,37,287,745,634,794,324,323,76,576,45,788,39,78,363,837,455,38,502,964,356,236,243,268,920,59,620,797,137,930,824,613,640,634,331,75,20,424,49,896,203), 136000)18  }19 20  test("test5") {21    assertEquals(Main.numberOfSubsequences(554,726,312,607,51,859,471,711,782,273,563,447,595,68,522,591,530,710,800,633,301,935,931,485,267,163,231,612,814,618,257,11,270,349,938,919,253,938,143,449,236,484,979,569,823,26,473,709,981,310,937,582,642,117,885,794,125,36,853,692,452,539,901,551,999,127,913,532,68,987,201,8,998,141,401,438,759,19,552,698,530,686,514,167,294,285,514,852,299,548,418,565,284,864,736,338,778,614,278,464,327,391,527,887,581,439,91,811,656,136,949,888,820,268,393,470,946,517,276,521,893,906,270,336,13,444,57,328), 46)22  }23 24  test("test6") {25    assertEquals(Main.numberOfSubsequences(215,54,712,806,815,931,923,410,409,583,701,928,557,254,940,891,722,78,493,995,333,587,387,549,948,907,514,267,766,93,163,74,764,732,322,240,461,289,324,78,915,172,71,87,344,43,573,944,470,801,78,894,990,5,426,748,366,349,983,556,673,996,176,747,800,57,516,834,114,940,577,237,906,535,698,615,334,155,382,119,786,950,266,785,824,83,457,493,38,234,294,623,71,960,777,555,280,143,199,850,870,394,724,921,79,626,595,369,606,442,260,165,800,882,913,456,880,370,179,623,553,537,494,900,280,524,526,121,671,222,962,875,962,562,774,223,87,100,164,465,745,985,902,143,9,358,898,12,500,199,404,179,425,482,819,38,271,252,644,225,290,694,658,206,615,212,490,472,636,8,51,966,169,946,749,798,107,210,998,291,334,495,447,36,528,415,369,13,497,868,880,144,503,319,559,878,974,62,766,556,402,452,968,659,737,416,405,777,73,162,762,95,988,155,254,153,415,858,152,570,158,948,700,654,941,895,137,786,546,436,151,394,765,445,980,198,652,557,81,810,183,116,924,699,489,313,825,934,240,555,706,808,616,639,11,143,199,925,741,690,307,161,983,655,632,724,507,614,652,706,313,554,598,458,566,603,434,331,695,770,690,706,254,725,681,250,89,286,860,885,276,166,639,404,475,438,1000,354,529,68,581,507,433,156,180,506,585,162,959,391,762,399,112,3,260,364,523,325,443,336,966,23,332,19,216,84,999,846,522,906,7,898,953,244,600,642,648,390,973,209,438,829,433,807,196,978,168,512,218,835,735,307,120,880,739,219,41,446,750,619,850,140,243,275,353,798,611,896,449,593,997,748,384,881,443,902,769,641,719,535,591,948,592,691,266,62,996,334,460,223,103,413,392,49,648,881,643,225,722,658,257,803,655,285,243,5,311,248,430,895,350,610,222,991,952,891,596,130,418,697,211,33,135,128,955,836,625,490,258,841,99,355,753,810,607,510,679,639,911,404,603,680,247,10,509,503,813,678,346,63,647,522,885,48,492,91,990,935,569,766,329,504,336,41,672,491,357,856,328,894,625,662,821,591,240,13,997,836,259,231,970,943,655,402,643,379,201,702,233,637,323,650,738,411,709,196,638,723,334,737,518,35,713,525,866,18,171,292,272,427,195,670,704,724,608,57,867,304,94,826,401,197,854,439,451,981,108,999,364,104,251,557,900,155,253,415,971,389,64,363,442,496,369,657,985,269,866,57,532,678,786,584,564,663,585,164,422,940,330,401,855,45,287,928,456,667,551,921,252,411,968,372,715,420,21,572,373,499,528,163,519,274,628,365,937,433,912,580,253,56,933,741,134,510,394,54,352,531,408,606,523,55,564,461,690,398,245,813,819,130,721,452,624,555,216,988,992,483,566,687,548,367,786,15,672,889,869,317,618,571,131,525,386,137,328,843,612,336,644,548,604,41,663,241,776,232,668,596,65,772,98,59,12,877,502,58,900,519,943,220,476,111,476,418,860,643,759,754,408,808,1000,626,383,675,455,268,268,571,915,132,192,573,274,720,872,819,369,497,143,109,438,264,750,944,39,496,274,295,84,359,465,605,133,915,906,682,541,134,76,51,823,425,490,653,656,745,428,289,387,755,937,513,578,480,429,706,82,740,404,1,248,392,209,106,575,590,128,253,559,481,134,452,513,858,310,511,812,142,730,694,144,431,209,420,759,91,257,549,794,39,508,559,713,38,778,507,200,17,95,462,186,873,616,409,635,97,200,91,375,815,625,544,874,306,788,64,942,626,719,266,881,828,233,201,8,547,394,720,314,628,885,538,602,94,616,4,188,873,901,695,287,953,469,787,65,76,132,937,908,455,551,404,850,762,670,56,371,161,412,671,740,60,908,846,549,56,280,940,417,839,732,77,646,831,771,426,102,775,509,795,910,701,151,520,79,771,771,155,945,436,612,68,606,164,806,20,423,561,814,885,121,501,199,704,467,895,412,549,853,180,204,322,555,748,750,711,809,362,861,413,417,880,709,767,161,566,370,673,478,240,204,189,698,496,92,433,415,765,525,945,858,420,198,562,216,722,434,859,231,8,935,499,672,857,39,381,707,265,286,976,613,119,763,913,381,349,595), 254317)26  }27 28  test("test7") {29    assertEquals(Main.numberOfSubsequences(902,905,731,604,350,252,535,709,601,399,372,843,927,576,311,428,736,323,378,22,263,568,181,422,512,577,275,175,283,701,861,518,290,624,123,727,284,880,759,817,504,258,720,188,349,516,202,492,663,233,391,33,311,643,259,162,208,726,241,388,89,327,134,631,433,144,574,12,600,447,138,13,908,84,48,529,853,747,13,227,127,721,832,399,949,360,331,538,153,534,378,943,800,221,535,821,355,332,794,576,887,827,29,895,381,658,155,646,999,798,543,300,92,479,577,23,194,956,323,2,548,592,317,693,908,241,366,688,378,307,124,749,446,585,390,140,238,231,324,79,522,880,623,950,234,695,404,937,461,28,483,572,636,980,267,99,720,947,581,584,635,762,547,305,715,223,338,33,891,754,358,858,473,807,396,604,255,746,547,830,20,727,83,448,760,943,16,714,371,994,704,549,41,391,403,70,299,414,462,575,897,99,602,623,340,599,605,741,195,193,978,927,80,509,626,912,704,705,360,134,299,40,511,1000,519,44,886,529,963,1000,973,618,579,632,624,2,151,54,525,418,26,545,917,653,648,776,389,867,315,542,760,54,891,334,937,617,747,646,481,43,514,63,887,219,464,746,817,804,427,927,815,545,738,478,491,648,704,422,237,136,854,612,760,643,80,760,560,606,961,474,372,396,622,752,559,564,236,261,306,642,902,554,874,185,229,870,945,64,392,723,138,911,105,161,565,202,33,907,708,32,33,79,671,811,696,955,475,459,703,748,855,491,224,828,117,777,153,175,745,233,559,131,971,516,908,256,59,192,225,279,950,944,358,835,741,928,42,868,594,462,848,722,316,943,895,742,379,623,613,132,779,641,831,556,609,216,716,964,200,614,627,684,676,209,505,454,25,157,65,153,713,74,781,804,646,863,30,841,702,498,709,677,280,992,920,914,978,122,69,732,152,945,471,156,391,935,391,859,117,105,3,623,156,440,209,242,604,541,556,700,258,756,845,763,190,296,114,363,684,254,310,549,58,829,983,923,193,727,834,253,303,907,18,89,939,463,62,773,408,472,838,721,277,108,68,413,825,15,365,546,484,165,97,474,799,963,922,867,704,192,980,300,997,248,29,474,237,60,239,462,882,29,779,277,926,941,534,550,417,859,768,658,939,32,659,402,610,488,979,298,945,271,286,739,433,69,901,979,725,239,308,502,397,692,745,720,95,241,952,604,537,473,450,136,946,82,238,535,33,653,393,13,105,937,407,217,578,774,486,567,23,148,137,238,599,921,638,827,327,63,705,550,920,504,471,469,953,363,39,816,729,907,547,961,937,842,94,488,687,15,471,197,390,207,843,618,256,204,530,997,963,919,661,590,322,40,165,753,985,677,911,248,609,941,86,934,512,745,279,180,503,352,688,537,702,788,818,672,733,419,914,906,624,968,269,420,221,838,435,108,732,274,200,65,940,711,98,126,509,838,285,859,607,634,594,282,804,160), 59229)30  }31 32}33