Padheye.com : Discover Excellence

The Path To Discover Excellence

Saturday, 8 August 2020

Question Solved | The Card Game

 

Question:

One day, Fred and his N friends were playing a card game in which each player throws a cardwith a number written on it. 

The cards are such that a number X is written on front of the card, and the negative of that number is written on the back side of the card. This game has the following rules:

Each of the N players is asked to throw a card.After at the N vards are thrown. Fred has to flip one or more cards in consecutive order , only once.

Your task is to help Fred flip the cards in such a way that the sum of the numbers, on front face of the cards is the maximum.

 

Input Specification:

input1: An integer N denoting the number of cards(1<=N<=500)

input2: An integer array containing N integer, where the ith integer denotes

The value on the front of the card(-1000<=input2[i]<=1000)

Output Specifications:

Return the maximum sum of the numbers, on the front of the card

 

Example 1:

Input1 : 5

Input2 : -2 3 -1 -4 -2

Output: 8

Explanation:

Since Fred can flip consecutive cards only once, he chooses to flip the last three cards, which results in the maximum sum (-2+3+1+4+2) i.e. 8

Therefore 8 is returned as the output.

 

Example 2:

Input1: 5

Input2: -1 2 3 4 -5

Output: 13

Explanation:

Since Fred can flip consecutive cards only once, he chooses to flip the last three cards,

which results in the maximum sum (-1+2+3+4+5) i.e. 13

Therefore 13 is returned as the output.

 

Input:

5
-2 3 -1 -4 -2

Output:

13

Solution:

Python :

#https://codewindow.in
#join our telegram channel @codewindow

import sys

def minsubarraysum(n, a):
    min_sum = sys.maxsize
    curr_sum = 0;
    for i in range(0, n):
        curr_sum = curr_sum + a[i]
        if curr_sum < min_sum:
            min_sum = curr_sum
        if curr_sum > 0:
            curr_sum  = 0
    return min_sum;
    

n = int(input())
arr = list(map(int, input().split(" ")))
s = sum(arr)
min_sum = minsubarraysum(n, arr)
ans = s + min_sum * (-2)
print(ans)

C++ :

//https://codewindow.in
//join our telegram channel @codewindow

#include<bits/stdc++.h>
using namespace std;

int minsubarraysum(int a[], int n) {
    int min_sum = INT_MAX;
    int curr_sum = 0;
    for (int i = 0 ; i < n; i++) {
        curr_sum = curr_sum + a[i];
        if (curr_sum < min_sum)
            min_sum = curr_sum;
        if (curr_sum > 0)
            curr_sum  = 0;
    }
    return min_sum;
}

int main() {
    int n;
    cin >> n;
    int a[n];
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    int min_sum = minsubarraysum(a, n);
    int ans = sum + (min_sum * (-2));
    cout << ans;
}

No comments:

Post a Comment