## PROBLEM LINK:

**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)**.