SWEET - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice

Contest

Author: Ranjan Kumar Singh

Tester: Ved Prakash

Editorialist: Sudipto Roy

DIFFICULTY:

EASY

PRE-REQUISITES:

Kadane’s algorithm

PROBLEM:

After making a array of profit and loss on each sweet packet, problem simplifies to maximum subarray problem based on Kadane’s algorithm

EXPLANATION:

The student will get profit only when he picks sweet packet having higher value than the price of each packet as per the deal. Hence make an array of profit on each of the packet starting from 0 index up to n-1

Pseudo Code:


//make a profit array as
       for i=0 to n-1
          p[i]=(actual value of the packet)-(the cost for which he will get the sweet packet);
  //then apply Kadane's algorithm to find maximum subarray//
def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Complexity: O(N).

SOLUTIONS:

Setter’s solution

Tester’s solution

1 Like