Only passing 1 test other went wromg after solving for 1 day

#1

dont know whats wrong according to me its working fine i
have tried many sample test case manually . The idea that i have used is that i will find a regular subarray using kadens and some how know its starting point and ending point and then iterate from 0 to starting point find max subarray and add both subarrays if possible .Here is my code:

#2
#3

hEY @mdhammad139
Just one of the testcase where your logic fails
1
6
20 -100 20 10 -100 20
Here kadane will give 30 but if go circular then answer is 40

There can be multiple tet cases on which your logic will fail.

See this for correct Logic:
The maximum subarray sum in circular array is maximum of following

  • Maximum subarray sum in non circular array
  • Maximum subarray sum in circular array.

Example - [1,2,5,-2,-3,5]
Steps -

  • Find the maximum subarray sum using Kadane Algorithm. This is maximum sum for non circular array.

image
image890×300 25.4 KB

  • 1+2+5 = 8
  • For non circular sum,
    Step 1) find the minimum subarray sum of array.

image
image851×281 23.7 KB

-2-3 = -5
Step 2) Now find the total sum of array = 1 + 2 + 5 -2 - 3 + 5 = 8
Step 3) The max subarray sum for circular array = Total Sum - Minimum subarray Sum
= 8 - (-5) = 8 + 5 = 13
As illustrated above, substracting minimum subarray sum from total sum gives maximum circular subarray sum.
Answer = Max ( Non circular max sum + circular max sum ) = max(8,13) = 13

#4

sir i have updated my code now its giving correct answer for the test case u mentioned but this time no test case is passing when i submit

#5

I told you that there can be multiple testcases where your code will fail, Again share your code and I will again give you another test case if you want.
Or stick to the correct logic.

#6
#7

Failing for

4
8
-1 40 -14 7 6 5 -4 -1
8
10 -3 -4 7 6 5 -4 -1
5 
-5 3 4 -2 1
6
3 -10 2 1 -2 8

OUTPUT

52
23
7
12
#8

okay sir i will apply yr mentioned logic

#9

thanx …

1 Like