Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Added tasks 3572-3579#1993

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
javadev merged 9 commits intojavadev:mainfromjscrdev:tasks-3572-3579
Jun 10, 2025
Merged
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
package g3501_3600.s3572_maximize_ysum_by_picking_a_triplet_of_distinct_xvalues;

// #Medium #Array #Hash_Table #Sorting #Greedy #Heap_Priority_Queue
// #2025_06_10_Time_2_ms_(100.00%)_Space_64.25_MB_(40.62%)

public class Solution {
public int maxSumDistinctTriplet(int[] x, int[] y) {
int index = -1;
int max = -1;
int sum = 0;
for (int i = 0; i < y.length; i++) {
if (y[i] > max) {
max = y[i];
index = i;
}
}
sum += max;
if (max == -1) {
return -1;
}
int index2 = -1;
max = -1;
for (int i = 0; i < y.length; i++) {
if (y[i] > max && x[i] != x[index]) {
max = y[i];
index2 = i;
}
}
sum += max;
if (max == -1) {
return -1;
}
max = -1;
for (int i = 0; i < y.length; i++) {
if (y[i] > max && x[i] != x[index] && x[i] != x[index2]) {
max = y[i];
}
}
if (max == -1) {
return -1;
}
sum += max;
return sum;
}
}
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
3572\. Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values

Medium

You are given two integer arrays `x` and `y`, each of length `n`. You must choose three **distinct** indices `i`, `j`, and `k` such that:

* `x[i] != x[j]`
* `x[j] != x[k]`
* `x[k] != x[i]`

Your goal is to **maximize** the value of `y[i] + y[j] + y[k]` under these conditions. Return the **maximum** possible sum that can be obtained by choosing such a triplet of indices.

If no such triplet exists, return -1.

**Example 1:**

**Input:** x = [1,2,1,3,2], y = [5,3,4,6,2]

**Output:** 14

**Explanation:**

* Choose `i = 0` (`x[i] = 1`, `y[i] = 5`), `j = 1` (`x[j] = 2`, `y[j] = 3`), `k = 3` (`x[k] = 3`, `y[k] = 6`).
* All three values chosen from `x` are distinct. `5 + 3 + 6 = 14` is the maximum we can obtain. Hence, the output is 14.

**Example 2:**

**Input:** x = [1,2,1,2], y = [4,5,6,7]

**Output:** \-1

**Explanation:**

* There are only two distinct values in `x`. Hence, the output is -1.

**Constraints:**

* `n == x.length == y.length`
* <code>3 <= n <= 10<sup>5</sup></code>
* <code>1 <= x[i], y[i] <= 10<sup>6</sup></code>
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
package g3501_3600.s3573_best_time_to_buy_and_sell_stock_v;

// #Medium #Array #Dynamic_Programming #2025_06_10_Time_10_ms_(99.46%)_Space_44.46_MB_(97.36%)

public class Solution {
public long maximumProfit(int[] prices, int k) {
int n = prices.length;
long[] prev = new long[n];
long[] curr = new long[n];
for (int t = 1; t <= k; t++) {
long bestLong = -prices[0];
long bestShort = prices[0];
curr[0] = 0;
for (int i = 1; i < n; i++) {
long res = curr[i - 1];
res = Math.max(res, prices[i] + bestLong);
res = Math.max(res, -prices[i] + bestShort);
curr[i] = res;
bestLong = Math.max(bestLong, prev[i - 1] - prices[i]);
bestShort = Math.max(bestShort, prev[i - 1] + prices[i]);
}
long[] tmp = prev;
prev = curr;
curr = tmp;
}
return prev[n - 1];
}
}
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
3573\. Best Time to Buy and Sell Stock V

Medium

You are given an integer array `prices` where `prices[i]` is the price of a stock in dollars on the <code>i<sup>th</sup></code> day, and an integer `k`.

You are allowed to make at most `k` transactions, where each transaction can be either of the following:

* **Normal transaction**: Buy on day `i`, then sell on a later day `j` where `i < j`. You profit `prices[j] - prices[i]`.

* **Short selling transaction**: Sell on day `i`, then buy back on a later day `j` where `i < j`. You profit `prices[i] - prices[j]`.


**Note** that you must complete each transaction before starting another. Additionally, you can't buy or sell on the same day you are selling or buying back as part of a previous transaction.

Return the **maximum** total profit you can earn by making **at most** `k` transactions.

**Example 1:**

**Input:** prices = [1,7,9,8,2], k = 2

**Output:** 14

**Explanation:**

We can make $14 of profit through 2 transactions:

* A normal transaction: buy the stock on day 0 for $1 then sell it on day 2 for $9.
* A short selling transaction: sell the stock on day 3 for $8 then buy back on day 4 for $2.

**Example 2:**

**Input:** prices = [12,16,19,19,8,1,19,13,9], k = 3

**Output:** 36

**Explanation:**

We can make $36 of profit through 3 transactions:

* A normal transaction: buy the stock on day 0 for $12 then sell it on day 2 for $19.
* A short selling transaction: sell the stock on day 3 for $19 then buy back on day 4 for $8.
* A normal transaction: buy the stock on day 5 for $1 then sell it on day 6 for $19.

**Constraints:**

* <code>2 <= prices.length <= 10<sup>3</sup></code>
* <code>1 <= prices[i] <= 10<sup>9</sup></code>
* `1 <= k <= prices.length / 2`
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
package g3501_3600.s3574_maximize_subarray_gcd_score;

// #Hard #Array #Math #Enumeration #Number_Theory
// #2025_06_10_Time_13_ms_(100.00%)_Space_45.07_MB_(78.08%)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

@SuppressWarnings("unchecked")
public class Solution {
public long maxGCDScore(int[] nums, int k) {
int mx = 0;
for (int x : nums) {
mx = Math.max(mx, x);
}
int width = 32 - Integer.numberOfLeadingZeros(mx);
List<Integer>[] lowbitPos = new List[width];
Arrays.setAll(lowbitPos, i -> new ArrayList<>());
int[][] intervals = new int[width + 1][3];
int size = 0;
long ans = 0;
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
int tz = Integer.numberOfTrailingZeros(x);
lowbitPos[tz].add(i);
for (int j = 0; j < size; j++) {
intervals[j][0] = gcd(intervals[j][0], x);
}
intervals[size][0] = x;
intervals[size][1] = i - 1;
intervals[size][2] = i;
size++;
int idx = 1;
for (int j = 1; j < size; j++) {
if (intervals[j][0] != intervals[j - 1][0]) {
intervals[idx][0] = intervals[j][0];
intervals[idx][1] = intervals[j][1];
intervals[idx][2] = intervals[j][2];
idx++;
} else {
intervals[idx - 1][2] = intervals[j][2];
}
}
size = idx;
for (int j = 0; j < size; j++) {
int g = intervals[j][0];
int l = intervals[j][1];
int r = intervals[j][2];
ans = Math.max(ans, (long) g * (i - l));
List<Integer> pos = lowbitPos[Integer.numberOfTrailingZeros(g)];
int minL = pos.size() > k ? Math.max(l, pos.get(pos.size() - k - 1)) : l;
if (minL < r) {
ans = Math.max(ans, (long) g * 2 * (i - minL));
}
}
}
return ans;
}

private int gcd(int a, int b) {
while (a != 0) {
int tmp = a;
a = b % a;
b = tmp;
}
return b;
}
}
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
3574\. Maximize Subarray GCD Score

Hard

You are given an array of positive integers `nums` and an integer `k`.

You may perform at most `k` operations. In each operation, you can choose one element in the array and **double** its value. Each element can be doubled **at most** once.

The **score** of a contiguous **subarray** is defined as the **product** of its length and the _greatest common divisor (GCD)_ of all its elements.

Your task is to return the **maximum** **score** that can be achieved by selecting a contiguous subarray from the modified array.

**Note:**

* The **greatest common divisor (GCD)** of an array is the largest integer that evenly divides all the array elements.

**Example 1:**

**Input:** nums = [2,4], k = 1

**Output:** 8

**Explanation:**

* Double `nums[0]` to 4 using one operation. The modified array becomes `[4, 4]`.
* The GCD of the subarray `[4, 4]` is 4, and the length is 2.
* Thus, the maximum possible score is `2 × 4 = 8`.

**Example 2:**

**Input:** nums = [3,5,7], k = 2

**Output:** 14

**Explanation:**

* Double `nums[2]` to 14 using one operation. The modified array becomes `[3, 5, 14]`.
* The GCD of the subarray `[14]` is 14, and the length is 1.
* Thus, the maximum possible score is `1 × 14 = 14`.

**Example 3:**

**Input:** nums = [5,5,5], k = 1

**Output:** 15

**Explanation:**

* The subarray `[5, 5, 5]` has a GCD of 5, and its length is 3.
* Since doubling any element doesn't improve the score, the maximum score is `3 × 5 = 15`.

**Constraints:**

* `1 <= n == nums.length <= 1500`
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
* `1 <= k <= n`
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
package g3501_3600.s3575_maximum_good_subtree_score;

// #Hard #Array #Dynamic_Programming #Depth_First_Search #Tree #Bit_Manipulation #Bitmask
// #2025_06_10_Time_92_ms_(98.73%)_Space_55.23_MB_(11.71%)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

@SuppressWarnings("unchecked")
public class Solution {
private int digits = 10;
private int full = 1 << digits;
private long neg = Long.MIN_VALUE / 4;
private long mod = (long) 1e9 + 7;
private List<Integer>[] tree;
private int[] val;
private int[] mask;
private boolean[] isOk;
private long res = 0;

public int goodSubtreeSum(int[] vals, int[] par) {
int n = vals.length;
val = vals;
mask = new int[n];
isOk = new boolean[n];
for (int i = 0; i < n; i++) {
int m = 0;
int v = vals[i];
boolean valid = true;
while (v > 0) {
int d = v % 10;
if (((m >> d) & 1) == 1) {
valid = false;
break;
}
m |= 1 << d;
v /= 10;
}
mask[i] = m;
isOk[i] = valid;
}
tree = new ArrayList[n];
Arrays.setAll(tree, ArrayList::new);
int root = 0;
for (int i = 1; i < n; i++) {
tree[par[i]].add(i);
}
dfs(root);
return (int) (res % mod);
}

private long[] dfs(int u) {
long[] dp = new long[full];
Arrays.fill(dp, neg);
dp[0] = 0;
if (isOk[u]) {
dp[mask[u]] = val[u];
}
for (int v : tree[u]) {
long[] child = dfs(v);
long[] newDp = Arrays.copyOf(dp, full);
for (int m1 = 0; m1 < full; m1++) {
if (dp[m1] < 0) {
continue;
}
int remain = full - 1 - m1;
for (int m2 = remain; m2 > 0; m2 = (m2 - 1) & remain) {
if (child[m2] < 0) {
continue;
}
int newM = m1 | m2;
newDp[newM] = Math.max(newDp[newM], dp[m1] + child[m2]);
}
}
dp = newDp;
}
long best = 0;
for (long v : dp) {
best = Math.max(best, v);
}
res = (res + best) % mod;
return dp;
}
}
Loading
[8]ページ先頭
©2009-2025 Movatter.jp