mahmoud_arafa's blog

Hackerrank — Maximise Sum
By mahmoud_arafa, 10 years ago, In English

Hello. I'm getting WA for this problem.

Here is the problem link.

Here is my code link.

Can anyone help me with a test case?

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

Kadane's Algorithm is not what this problem asks you about.

Your task is to maximize reminder modulo M, not sum itself.

If M=7 then 6 is better than 14, because 6 gives 6 modulo 7, and 14 gives 0 modulo 7 (and 6 is, obviously, more than 0).

Your solution will fail on following test 

3 5
1 2 2

Here is my solution from a contest.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -47 Vote: I do not like it

    Well, I know what does the problem ask me about, but I think that we can modify Kadane's Algorithm to solve this problem. Sum solutions can be converted to Mod solutions.

    I read the editorial of this problem and I almost got the idea but I prefer to edit my ideas. Please notify me if you can solve this problem by modifying Kadane's.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
LL sum = 0 , ans = 0 ;
        set S ;
        S.insert(0) ;
        set :: iterator it ;
        for(int i=1;i<=n;i++){
            sum += A[i] ;
            sum %= m ;
            it = S.upper_bound(sum) ;
            if(it != S.end())
                ans = max(ans,sum-(*it)+m) ;
            else
                ans = max(ans,sum) ;
            S.insert(sum) ;
        }

Here is my idea for this solution. Firstly as mentioned by I_love_Tanya_Romanova this problem is not what you have thought earlier. so , suppose you are maintaining curr_sum % m then you have to maximise the sum of the array ending at each index i then take maximum of all. let us consider curr_sum[i] denotes the sum of all elements from 1 to i % m now to maximise this there are two cases only decrease the smallest value less than curr_sum[i] from curr_sum which is obviously 0 else you can subtract the value just greater than curr_sum[i] (consider this value as x). we can see curr_sum[i] — x is negative so we have to add m to it which implies we have to maximise this (curr_sum[i] — x + m) or (m+curr_sump[i] — x) so take the smallest value greater than curr_sum[i] which can be easily find by maintaining a set (denoting by S in my code). hope this is useful in some way or other.

→ Reply